Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

basic.ts
Replay: real traced execution (multi-file project)
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 output = [];
function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }
preorder(root);
console.log(`[${output.join(", ")}]`);

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

    1class Node {2  value: number;
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[] → [4]output4node

  3. output ← [4, 2]

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

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

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

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

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

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

    21const output = [];22function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }23preorder(root);
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. class Node

    1class Node {2  value: number;
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

Implementation notes

  • The sample tree uses the typed Node class with value: number and nullable left and right references, then allocates the same 4(2(1,3),6(5,7)) shape rendered by render.
  • const output = [] is filled by output.push(node.value). The checked source relies on inference for the output array and leaves preorder(node) without an explicit parameter annotation.
  • The recursive function returns immediately on node === null; otherwise it records the current value, then calls preorder(node.left) and preorder(node.right). Each non-null child visit appears as another call-stack frame before returning through the null leaf calls.
  • The trace records visit-before-children states for nodes 4, 2, 1, 3, 6, 5, 7, growing output from [] through [4, 2, 1, 3, 6, 5] to [4, 2, 1, 3, 6, 5, 7].
  • console.log(\[${output.join(", ")}]`)prints[4, 2, 1, 3, 6, 5, 7]`. Visible allocation is the tree, output array, and joined output string; traversal mutates only the output array, not the node links.