LietCode
Binary Tree Level Order Traversal (Medium)

Binary Tree Level Order Traversal (Medium)

Abhi's photo
Abhi
·

2 min read

1) Explain the problem

We need to perform a level order traversal on a binary tree. This means visiting each node level by level from left to right and returning the values of the nodes in this order.

2) Short easy to remember solution/approach

Use a queue to keep track of nodes at each level. Start with the root node, and for each node, add its children to the queue. Process nodes level by level until the queue is empty.

3) Solution in Javascript with code commenting

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function levelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const currentNode = queue.shift();
            currentLevel.push(currentNode.val);

            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }

        result.push(currentLevel);
    }

    return result;
}

// Example usage:
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

console.log(levelOrder(root)); // Output: [[1], [2, 3], [4, 5, 6, 7]]

4) Explanation of the solution in an easy-to-understand way. Explain it like a 10-year-old.

Imagine you are in a theater, and there are rows of seats. You want to see who is sitting in each row from the front to the back. You start at the front row, look at everyone sitting there, and then move to the next row, and so on, until you reach the back row.

5) Code explanation in pointers

  • Define a TreeNode class to represent each node in the tree.

  • Create a levelOrder function that:

    • Returns an empty array if the root is null.

    • Initializes an empty result array and a queue with the root node.

    • While the queue is not empty:

      • Determine the number of nodes at the current level (levelSize).

      • Initialize an array for the current level.

      • For each node at the current level:

        • Dequeue the node, add its value to the current level array.

        • Enqueue its left and right children (if any).

      • Add the current level array to the result array.

    • Return the result array.

6) Complexities

  • Time Complexity: (O(n)) - Each node is visited once.

  • Space Complexity: (O(n)) - The queue holds at most the number of nodes in the last level, and the result array holds all node values.

TreeTrees