Tree Traversals

You have a binary tree sitting in memory — a root, its children, their children, fanning out to the leaves. Sooner or later you need to do something to every node: print them, add them up, copy them, free their memory, or turn an expression tree into an answer. But a tree isn't a line — there is no obvious "first, second, third". So in what order do you visit the nodes?

Traversing a tree means visiting every node exactly once in some systematic order. The three classic orders are all depth-first — they plunge all the way down one branch before backing up to try another — and each is defined recursively, because a tree is made of smaller trees: a node, plus a left subtree and a right subtree, each of which is itself a binary tree. Handle the node, recurse into the left subtree, recurse into the right subtree — the only question is when you handle the node relative to those two recursions. Answer that three different ways and you get the three traversals:

In-order — left subtree, then the node, then right subtree (L · N · R).
Pre-order — the node first, then left subtree, then right subtree (N · L · R).
Post-order — left subtree, then right subtree, and the node last (L · R · N).

Notice the node (N) simply slides from the middle, to the front, to the back. That one choice is the entire difference — and it gives each traversal a personality and a favourite job, as we'll see.

The recursive definitions

Each traversal is three lines of the same three ingredients — recurse left, visit node, recurse right — just reshuffled. The base case is always the same: an empty subtree (a null child) has nothing to visit, so we stop. Here are all three, side by side; read them and watch the visit(node) line march from bottom, to top, to bottom:

// "Visit" here means: do the thing — print it, add it, whatever the job is. function inOrder(node: TreeNode | null): void { if (node === null) return; // base case: empty subtree, nothing to do inOrder(node.left); // 1. the whole LEFT subtree visit(node); // 2. THEN this node ← node in the MIDDLE inOrder(node.right); // 3. THEN the whole RIGHT subtree } function preOrder(node: TreeNode | null): void { if (node === null) return; visit(node); // 1. this node FIRST ← node at the FRONT preOrder(node.left); // 2. then the LEFT subtree preOrder(node.right); // 3. then the RIGHT subtree } function postOrder(node: TreeNode | null): void { if (node === null) return; postOrder(node.left); // 1. the whole LEFT subtree postOrder(node.right); // 2. then the whole RIGHT subtree visit(node); // 3. this node LAST ← node at the BACK }

Three functions, one skeleton, one moved line. If you can remember "the node is visited in the middle / first / last", you can reconstruct all three from memory in an exam.

Walking one small tree

Let's put a real tree under all three. We'll use this seven-node binary search tree, built from 50, 30, 70, 20, 40, 60, 80:

50 / \ 30 70 / \ / \ 20 40 60 80

Each figure below steps through one traversal, lighting up nodes in the order they are visited and stamping each with its position (1st, 2nd, 3rd …). Press play and follow the recursion diving down the left, popping back up, then heading right.

In-order (L · N · R) — 20, 30, 40, 50, 60, 70, 80

In-order slides all the way down to the leftmost node first, then works rightward — and out come the values in sorted order. That is no accident, and it's a favourite exam fact (more below).

Pre-order (N · L · R) — 50, 30, 20, 40, 70, 60, 80

Pre-order visits each node the moment it arrives, before exploring beneath it, so the root comes out first and every parent appears before its children. That's exactly the order you'd want to copy a tree or write it to a file: create each node, then its descendants.

Post-order (L · R · N) — 20, 40, 30, 60, 80, 70, 50

Post-order finishes both subtrees before touching the node, so every child appears before its parent and the root comes out last. That is perfect for jobs where a node's work depends on its children being done first — deleting a tree (free the children, then the parent) or evaluating an expression tree (compute both operands, then combine).

All three, in running code

Here is the same little tree in TypeScript, with all three traversals collecting the values they visit into an array so we can print the order. Press Run and compare the three lines against the walk-throughs above:

type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null }; // Build the tree: 50 // 30 70 // 20 40 60 80 const leaf = (v: number): TreeNode => ({ value: v, left: null, right: null }); const tree: TreeNode = { value: 50, left: { value: 30, left: leaf(20), right: leaf(40) }, right: { value: 70, left: leaf(60), right: leaf(80) }, }; function inOrder(node: TreeNode | null, out: number[]): void { if (node === null) return; // base case inOrder(node.left, out); // LEFT subtree out.push(node.value); // then NODE inOrder(node.right, out); // then RIGHT subtree } function preOrder(node: TreeNode | null, out: number[]): void { if (node === null) return; out.push(node.value); // NODE first preOrder(node.left, out); // then LEFT preOrder(node.right, out); // then RIGHT } function postOrder(node: TreeNode | null, out: number[]): void { if (node === null) return; postOrder(node.left, out); // LEFT postOrder(node.right, out); // then RIGHT out.push(node.value); // NODE last } const inR: number[] = []; inOrder(tree, inR); const preR: number[] = []; preOrder(tree, preR); const postR: number[] = []; postOrder(tree, postR); console.log("in-order: " + inR.join(", ")); console.log("pre-order: " + preR.join(", ")); console.log("post-order: " + postR.join(", "));

Try editing the tree — swap a leaf, add a subtree — and re-run. However you reshape it, in-order on this BST always comes back sorted, pre-order always starts at the root, and post-order always ends at the root.

It is tempting to think the three traversals are three completely different algorithms. They aren't. They visit the same nodes, make the same recursive calls, and dive down the same branches in the same directions. The one and only difference is when you visit the node — before its two subtree recursions (pre), between them (in), or after both (post). Move that single visit(node) line and you've converted one into another. Don't memorise three unrelated procedures; memorise one skeleton and the position of that line.

And commit this to memory, because examiners love it: an in-order traversal of a binary search tree outputs the values in sorted (ascending) order. The reason is the BST rule — everything in the left subtree is smaller than the node, everything in the right is larger — so "left, node, right" is exactly "smaller values, this value, larger values" at every step. (It only sorts for a BST; run in-order on a tree that isn't ordered and you'll just get some order, not a sorted one.)

Write (3 + 4) \times 5 as a tree — operators at the branch nodes, numbers at the leaves — and the two "backwards" traversals suddenly mean something. Read it pre-order and you get × + 3 4 5: that's Polish notation. Read it post-order and you get 3 4 + 5 ×: that's Reverse Polish Notation (RPN), the very notation old HP calculators and countless stack-based virtual machines use, because you can evaluate it left-to-right with a single stack and no brackets at all. So post-order isn't a curiosity — it's how a computer actually computes an expression: evaluate both operands (the children) first, then apply the operator (the node). The traversal order is the evaluation order.