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].

Basic Implementation

basic.ts 
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));

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.
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.