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.js 
class TreeNode {
    constructor(value, left, right) {
        this.value = value;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

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

const output = [];
function inorder(node) {
    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

  • JavaScript: a small class TreeNode holds value, left, and right. 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.