Trees

In-Order Traversal (BST)

Recurse left, visit(node), recurse right. On a binary search tree, this emits values in ascending order — a useful invariant to teach.

Algorithm

Canonical tree 4(2(1, 3), 6(5, 7)) is a balanced BST. In-order traversal yields [1, 2, 3, 4, 5, 6, 7].

in-order recursion `inorder(node.left); output.push(node.value); inorder(node.right);`
BST invariant The same recursion on a binary search tree always emits values in ascending order.

Basic Implementation

basic.ts
Replay: real traced execution (multi-file project)
class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(value: number, left: TreeNode | null, right: TreeNode | null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

const n1: TreeNode = new TreeNode(1, null, null);
const n3: TreeNode = new TreeNode(3, null, null);
const n2: TreeNode = new TreeNode(2, n1, n3);
const n5: TreeNode = new TreeNode(5, null, null);
const n7: TreeNode = new TreeNode(7, null, null);
const n6: TreeNode = new TreeNode(6, n5, n7);
const root: TreeNode = new TreeNode(4, n2, n6);

const output: number[] = [];
function inorder(node: TreeNode | null): void {
    if (node === null) {
        return;
    }
    inorder(node.left);
    output.push(node.value);
    inorder(node.right);
}
inorder(root);
console.log(JSON.stringify(output));

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

    20const output: number[] = [];21function inorder(node: TreeNode | null): void {
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[] → [1]output

  3. output ← [1, 2]

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1, 2] → [1, 2, 3]output

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

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1, 2, 3] → [1, 2, 3, 4]output

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

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

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

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

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

    25inorder(node.left);26output.push(node.value);27inorder(node.right);
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]output

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

    29inorder(root);30console.log(JSON.stringify(output));
    values this step[1, 2, 3, 4, 5, 6, 7]stdout[1, 2, 3, 4, 5, 6, 7]output

Complexity

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

Implementation notes

  • TypeScript: a small class TreeNode holds value: number, left: TreeNode | null, and right: TreeNode | null. The recursion is the smallest possible reusable shape.
  • The replay shows the running output array and the visited node value on each visit frame.