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.

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 output = [];
function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }
preorder(root);
console.log(`[${output.join(", ")}]`);

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.
preorder Preorder records the current node before visiting left and right subtrees.