Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this JavaScript DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

basic.js
Replay: real traced execution (multi-file project)
class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function render(node) {
  if (node === null) return "_";
  if (node.left === null && node.right === null) return String(node.value);
  return `${node.value}(${render(node.left)},${render(node.right)})`;
}
function sampleTree() {
  return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}

const root = sampleTree();
const queue = [root];
const output = [];
while (queue.length > 0) { const node = queue.shift(); output.push(node.value); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); }
console.log(`[${output.join(", ")}]`);

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1class Node {2  constructor(value, left = null, right = null) {
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    17const root = sampleTree();18const queue = [root];19const output = [];
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. class Node

    1class Node {2  constructor(value, left = null, right = null) {
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • The tree uses JavaScript Node objects with value, left, and right references. Missing children are null; traversal reads those references without mutating the tree.
  • The queue is a mutable Array seeded as [root]. Each loop uses queue.shift() to dequeue the front node, which preserves breadth-first order but reindexes a normal JavaScript array, making each shift O(n) in the current queue length.
  • Visited values are appended to output with output.push(node.value). Non-null child references are enqueued with queue.push(node.left) and queue.push(node.right).
  • The replay shows queue/output states [4] -> [2, 6] with output [4], then [6, 1, 3] with [4, 2], then [1, 3, 5, 7] with [4, 2, 6], ending at queue [] and output [4, 2, 6, 1, 3, 5, 7].
  • console.log(\[${output.join(", ")}]`)formats the deterministic stdout[4, 2, 6, 1, 3, 5, 7]. Heap allocation is the seven-node sample tree, the queue array, the output array, and the strings created by join` and the template literal.