Opacity

Binary Tree Level Order Traversal

O(n)
O(n)

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).

Solution Approach
BFS

We'll use a Breadth-First Search (BFS) approach with a queue to traverse the tree level by level, collecting nodes at each level before moving to the next.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(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 node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
};

Explanation

  • 1.Check if the root is null. If so, return an empty array.
  • 2.Initialize a queue with the root node and a result array.
  • 3.While the queue is not empty, process nodes level by level:
  • a.For each level, process all nodes currently in the queue.
  • b.Add each node's value to the current level array.
  • c.Add the node's left and right children to the queue if they exist.
  • 4.Add the current level array to the result.
  • 5.Return the result array containing all levels.