Binary Tree Level Order Traversal - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const QUEUED = 'queued', QUEUED_COLOR = 'gold';
const VISITED = 'visited', VISITED_COLOR = 'green';
const CURRENT_LEVEL = 'current_level', CURRENT_LEVEL_COLOR = 'gray'; 

function visMainFunction(treeInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const root = convertInputToTree(treeInput);
    if (!root) {
        notification('❌ <b>Empty tree.</b> No levels to traverse.');
        return [];
    }

    startPartialBatch();
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });
    const result = new VisArray2D();

    const queue = new VisQueue().options({ labelExtractionPolicy: (node) => '' + node.val });
    queue.enqueue(root);
    tree.makeVisManagerForNode(root).addClass(QUEUED);
    notification(`🟡 <b>Init:</b> Enqueued the root. It’s marked ${makeColoredSpan('queued', QUEUED_COLOR)} and will be processed in Level 0.`);

    endBatch();

    let levelIndex = 0;

    while (!queue.isEmpty()) {
        const levelSize = queue.size();
        const levelValues = new VisArray();

        startPartialBatch();
        highlightAllElements(queue);
        notification(`
            📦 <b>Processing Level ${levelIndex}</b><br>
            Taking a snapshot: <code>levelSize = ${levelSize}</code> (the number of nodes currently in the queue).<br>
            These <b>${levelSize}</b> nodes are highlighted with a ${makeColoredSpan(CURRENT_LEVEL_COLOR + ' background', CURRENT_LEVEL_COLOR)} to mark
            “<i>this level’s nodes</i>” and to distinguish them from the next level’s nodes that will be added to the queue during this iteration.<br>
            Any new children added to the queue in this iteration belong to the <b>next level</b> and will be processed in the <b>next iteration</b> — not in this one. <br><br>
            🧾 Also initialized an empty <code>levelValues</code> array to begin collecting node values for this level in their correct left-to-right order.
        `);
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.dequeue();
            const vm = tree.makeVisManagerForNode(node).removeClass(QUEUED);

            setCurrentNode(vm);
            notification(`
                🔵 Visiting the ${makeColoredSpan('current node', CURRENT_COLOR)}, just dequeued from the <b>front of the queue</b>.<br>
                Recording its value for this level by pushing it into the <code>levelValues</code> array, and checking its children to enqueue them (left first, then right) for the next level.
            `);

            levelValues.push(node.val);

            if (node.left) {
                tree.makeVisManagerForNode(node.left).addClass(QUEUED);
                queue.enqueue(node.left);
                notification(`
                    🟡 Left child of the ${makeColoredSpan('current node', CURRENT_COLOR)} is <b>enqueued</b> — 
                    it will appear in the queue for the <b>next level</b> and be processed in the next iteration.
                `);
            }

            if (node.right) {
                tree.makeVisManagerForNode(node.right).addClass(QUEUED);
                queue.enqueue(node.right);
                notification(`
                    🟡 Right child of the ${makeColoredSpan('current node', CURRENT_COLOR)} is <b>enqueued</b> — 
                    it will appear in the queue for the <b>next level</b> and be processed in the next iteration.
                `);
            }

            notification(`
                ✅ ${makeColoredSpan('Visited', VISITED_COLOR)}: Finished processing the ${makeColoredSpan('current node', CURRENT_COLOR)} — 
                all its children (if any) have been enqueued, and it’s now marked as ${makeColoredSpan('visited', VISITED_COLOR)}.
            `); 
            vm.removeClass(CURRENT).addClass(VISITED); 
        }

        result.push(levelValues);
        notification(`
            📥 <b>Level ${levelIndex} Complete:</b> All nodes in this level have been processed.<br>
            Their children (if any) are now queued for the <b>next level</b>.<br>
             The collected values for this level have been pushed into the <code>result</code> array.
        `);
        levelIndex++;
        endBatch();
    }

    notification(` 🏁 <b>Traversal complete.</b> The <code>result</code> now contains the level-by-level node values gathered during the traversal.<br> Returning the <code>result</code>.`);
    return result;
}

// --- Helpers --- 

let current = null; 

function setCurrentNode(vm) {
    if (current) current.removeClass(CURRENT);
    vm.addClass(CURRENT);
    current = vm;
}

function highlightAllElements(queue) {
    startBatch();
    for (let index = 0; index < queue.size(); index++) {
        queue.makeVisManagerForIndex(index).addClass(CURRENT_LEVEL);
    }
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(QUEUED, { backgroundColor: QUEUED_COLOR });
    setClassProperties(VISITED, { backgroundColor: VISITED_COLOR });
    setClassProperties(CURRENT_LEVEL, { backgroundColor: CURRENT_LEVEL_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

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

function explanationAndColorSchemaNotifications() {
  explanationNotification();

  notification(`
    🎨 <b>Visual Cues</b>
    <ul>
      <li>${makeColoredSpan('Current', CURRENT_COLOR)} → ${CURRENT_COLOR} border on the node being dequeued/processed.</li>
      <li>${makeColoredSpan('Queued', QUEUED_COLOR)} → ${QUEUED_COLOR} background on nodes that are currently in the queue.</li>
      <li>${makeColoredSpan('This level (queue snapshot)', CURRENT_LEVEL_COLOR)} → ${CURRENT_LEVEL_COLOR} background on the queue entries that belong to the <b>current</b> iteration (exactly <code>levelSize</code> items).</li>
      <li>${makeColoredSpan('Visited', VISITED_COLOR)} → ${VISITED_COLOR} background after a node is fully processed and its children (if any) are enqueued.</li>
    </ul>
  `);
}

Approach

We solve this problem using a Breadth-First Search (BFS) traversal, which visits all nodes at the same level before moving to the next level. BFS uses a queue (FIFO) to ensure nodes are processed in left-to-right order, since children are enqueued in the same order they should appear in the next level (left first, then right).

Base case: If the root is null, return an empty array — there are no levels to traverse.
Initialization: Enqueue the root node and prepare an empty 2D array result to store the values level by level.
Iterative processing: Continue while the queue is not empty (while (!queue.isEmpty())):
1. At the start of each iteration, take a snapshot of the queue size into a variable levelSize. This represents the number of nodes that belong to the current level. ⚠️ We take this snapshot before processing any nodes because, as we dequeue nodes and enqueue their children, the queue size may change, affecting which nodes belong to this level. Also, initialize an empty array levelValues to begin collecting the node values for this level in their correct left-to-right order.
2. Using this levelSize snapshot, process exactly that many nodes — these are all the nodes for the current level. For each dequeued node:
  - Record its value for this level by pushing it into the levelValues array.
  - Enqueue its children (left first, then right) for the next iteration, which will handle the next level.
3. After processing all levelSize nodes, push the collected level values (levelValues) into result.

📌 Why it works

The queue ensures that we always process nodes level by level and in left-to-right order because:

Children are enqueued in the same order they should appear in the next level (left first, then right).
Each iteration processes exactly one level’s nodes, determined by the levelSize snapshot taken at the start.

Return value: result, a 2D array where each inner array contains the node values of one level, processed from left to right per iteration.

Time Complexity

O(n), where n is the number of nodes — each node is enqueued and dequeued exactly once.

Space Complexity

O(w) excluding the output — where w is the maximum width of the tree (for the queue), which in the worst case can be O(n/2). The output itself also requires O(n) space, where n is the total number of nodes.

Input-1

Binary Tree Level Order Traversal - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

📌 Why it works

Time Complexity

Space Complexity