Binary Tree Level Order Traversal medium

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1] Output: [[1]]

Steps

1. Initialization: Create an empty array result to store the level order traversal. Initialize a queue queue with the root node. If the root is null, return an empty array.
2. Level Traversal: While the queue is not empty:
   • Get the size levelSize of the queue. This represents the number of nodes at the current level.
   • Create an empty array level to store the values of nodes at the current level.
   • Iterate levelSize times:
     • Dequeue a node from the queue.
     • Add the node's value to the level array.
     • Enqueue the node's left child (if it exists).
     • Enqueue the node's right child (if it exists).
   • Add the level array to the result array.
3. Return: Return the result array.

Explanation

The algorithm uses Breadth-First Search (BFS) to traverse the binary tree level by level. The queue acts as a FIFO (First-In, First-Out) data structure. Nodes are added to the queue level by level, ensuring that nodes at the same depth are processed together. The levelSize variable helps us process one level at a time.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function levelOrder(root: TreeNode | null): number[][] {
    const result: number[][] = [];
    if (!root) return result;

    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const level: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node!.val); // ! asserts that node is not null because we checked queue.length

            if (node!.left) {
                queue.push(node!.left);
            }
            if (node!.right) {
                queue.push(node!.right);
            }
        }
        result.push(level);
    }

    return result;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width (maximum number of nodes at any level) of the binary tree. In the worst-case scenario (a complete binary tree), W can be equal to N. The space complexity is dominated by the queue.