Tree Traversals: guided lesson

the story

Binary tree

Every tool here exists because something was too slow or broke without it. Here is what.

1857 · Arthur Cayley (the name "tree"); no single inventor of the linked binary tree in programs

In 1857 the mathematician Arthur Cayley published "On the theory of the analytical forms called trees" in the Philosophical Magazine. He was counting rooted, branching shapes while studying how calculus operators combine — and the name tree stuck. In programs, a node holding two links (left, right) became a standard building block of early list-processing and compilers; no one person is credited with it. Today every node in a Java TreeMap is built on it: a key and a value, left and right child references (plus a parent link and a red/black colour bit).

the problem it solved

Representing hierarchy and branching — anything where one thing splits into at most two smaller things of the same kind.

why it matters: without it

Hierarchies would be flattened into lists: every "find", "insert in order" or "evaluate this expression" becomes a linear scan.

sources: Cayley — On the theory of the analytical forms called trees (Philosophical Magazine, 1857) ↗ · Knuth — The Art of Computer Programming, Vol. 1: Fundamental Algorithms (§2.3 Trees) ↗

also in this chapter: Depth-first traversal (pre, in, post order) · Breadth-first traversal (level order) · Serialization with null markers

the idea

The idea in 30 seconds

A binary tree is a node with a value and at most two children — and each child is itself a binary tree.

A traversal visits every node once. Depth-first (pre, in, post order) goes deep using a stack; breadth-first (level order) goes level by level using a queue.

Many tree problems are just the right visiting order plus one line of work at each visit.

picture this

Your File Explorer folder tree, walked two ways. Depth-first: open Projects and everything inside it before you touch Downloads — that's how the Windows tree command prints folders (preorder). Breadth-first: list every top-level folder, then every folder one level down — so the first match you find is the shallowest one.

watch it

Preorder · inorder · postorder walk

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Preorder · inorder · postorder walk

Type pre, in or post. The call stack (right) is the path from the root to the current node; the output fills in when the node is *visited*.

loading simulation…

javajava.util.*

1class RecursiveDfs {2    /** Root, then left subtree, then right subtree. */3    static void preorder(TreeNode node, List<Integer> out) {4        if (node == null) return;5        out.add(node.val);                 // visit BEFORE the children6        preorder(node.left, out);7        preorder(node.right, out);8    }9 10    /** Left subtree, then root, then right subtree. */11    static void inorder(TreeNode node, List<Integer> out) {12        if (node == null) return;13        inorder(node.left, out);14        out.add(node.val);                 // visit BETWEEN the children15        inorder(node.right, out);16    }17 18    /** Left subtree, then right subtree, then root. */19    static void postorder(TreeNode node, List<Integer> out) {20        if (node == null) return;21        postorder(node.left, out);22        postorder(node.right, out);23        out.add(node.val);                 // visit AFTER the children24    }25}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Inorder without recursion

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Inorder without recursion

An explicit stack does exactly what the call stack did: remember the nodes we still have to come back to.

loading simulation…

javajava.util.*

1class IterativeDfs {2    static List<Integer> preorder(TreeNode root) {3        List<Integer> out = new ArrayList<>();4        if (root == null) return out;5        Deque<TreeNode> stack = new ArrayDeque<>();6        stack.push(root);7        while (!stack.isEmpty()) {8            TreeNode node = stack.pop();9            out.add(node.val);10            // push right first so left is popped (visited) first11            if (node.right != null) stack.push(node.right);12            if (node.left != null) stack.push(node.left);13        }14        return out;15    }16 17    static List<Integer> inorder(TreeNode root) {18        List<Integer> out = new ArrayList<>();19        Deque<TreeNode> stack = new ArrayDeque<>();20        TreeNode cur = root;21        while (cur != null || !stack.isEmpty()) {22            while (cur != null) {                    // dive as far left as possible23                stack.push(cur);24                cur = cur.left;25            }26            cur = stack.pop();                       // leftmost unvisited node27            out.add(cur.val);28            cur = cur.right;                         // then its right subtree29        }30        return out;31    }32 33    /** Postorder = reverse of a "root, right, left" preorder. */34    static List<Integer> postorder(TreeNode root) {35        List<Integer> out = new ArrayList<>();36        if (root == null) return out;37        Deque<TreeNode> stack = new ArrayDeque<>();38        stack.push(root);39        while (!stack.isEmpty()) {40            TreeNode node = stack.pop();41            out.add(node.val);42            if (node.left != null) stack.push(node.left);43            if (node.right != null) stack.push(node.right);44        }45        Collections.reverse(out);46        return out;47    }48}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 8