Binary Tree Level Order Traversal

Meta

Tree

BFS

Queue

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), as an array of arrays — one inner array per level.

Example:

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

Solution Walkthrough

Level order traversal is a direct application of Breadth-First Search (BFS) using a queue, with one extra trick: tracking how many nodes belong to the current level.

If root is null, return an empty array immediately.
Push root onto a queue.
While the queue is not empty:
- Record the current queue length as levelSize — this is exactly how many nodes are on the current level.
- Dequeue levelSize nodes one at a time, collecting their values into a currentLevel array, and enqueue each node's non-null children.
- Push currentLevel onto the result.

Each node is enqueued and dequeued exactly once, giving O(n) time complexity. Space complexity is O(w), where w is the maximum width of the tree (the queue never holds more than one level's worth of nodes at a time).

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 node = queue.shift();
            currentLevel.push(node.value);

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

        result.push(currentLevel);
    }

    return result;
}

Related Algorithms

Breadth-First Search (BFS) →

Queue →