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 TypeScript DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.ts 
class Node {
  value: number;
  left: Node | null;
  right: Node | null;
  constructor(value: number, left: Node | null = null, right: Node | null = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function render(node: Node | null): string {
  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(): Node {
  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(", ")}]`);

Complexity

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

Implementation notes

  • The traversal uses the typed Node class with value: number and nullable left and right references from the tree-build lesson.
  • const queue = [root] is inferred from the Node root, while const output = [] is filled with visited numeric values. The checked source relies on inference rather than explicit queue/output annotations.
  • Each loop runs under while (queue.length > 0) and calls queue.shift(). The replay never observes an undefined dequeue, though TypeScript's array shift() type is possibly undefined in stricter settings.
  • Visited values are appended with output.push(node.value). Non-null child references are enqueued with queue.push(node.left) and queue.push(node.right).
  • The trace records 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(", ")}]`)prints[4, 2, 6, 1, 3, 5, 7]`. Visible allocation is the sample tree, queue array, output array, and output string; traversal does not mutate nodes.
level order Level-order traversal uses a queue to visit shallower nodes first.