Tree traversals
Traversing a tree means visiting every node in a systematic order. Different orders suit different tasks, from printing sorted data to copying or deleting a tree.
Depth-first traversals
Depth-first traversals go as deep as possible before backtracking. Pre-order visits the node, then the left subtree, then the right. In-order visits left, then node, then right. Post-order visits left, then right, then node. Each visits every node once, O(n) time, using O(h) stack space for a tree of height h.
What each order is for
Pre-order is natural for copying a tree or serialising it, since parents come before children. In-order visits a binary search tree's keys in sorted order. Post-order processes children before parents, which suits deleting a tree, computing directory sizes, and evaluating expression trees.
Level-order traversal
Level-order, or breadth-first, traversal visits nodes level by level from left to right using a queue: enqueue the root; repeatedly dequeue a node, visit it, and enqueue its children. It finds the minimum depth, prints trees by level, and connects nodes on the same level. Its extra space is proportional to the widest level.
Iterative traversals
Recursive traversals are elegant but can overflow the call stack on very deep trees. Iterative versions use an explicit stack. For in-order: push nodes while moving left; when you cannot go further left, pop a node, visit it, then move to its right child and repeat. Morris traversal even achieves O(1) extra space by temporarily rewiring pointers.
Expression notation
Traversing an expression tree in different orders gives different notations. Pre-order gives prefix (Polish) notation, such as x + 3 4 2; in-order with brackets gives ordinary infix, (3 + 4) x 2; and post-order gives postfix (reverse Polish), 3 4 + 2 x, which a stack can evaluate directly.
Reconstructing trees
A binary tree with distinct values can be rebuilt uniquely from its pre-order and in-order sequences: the first pre-order element is the root, and its position in the in-order sequence splits the left and right subtrees, which are rebuilt recursively. Pre-order and post-order alone are not enough for general binary trees.
Traversal patterns in problems
Many tree problems are a traversal with extra work at each node. Checking if a tree is balanced is post-order: compute subtree heights, then compare. Finding the lowest common ancestor of two nodes, summing values along root-to-leaf paths, and serialising a tree into a string all follow the same template: decide what each node needs from its children and what it passes back.
Worked example
For the tree with root 8, children 3 and 10, where 3 has children 1 and 6, and 10 has right child 14: pre-order is 8, 3, 1, 6, 10, 14; in-order is 1, 3, 6, 8, 10, 14 (sorted, since it is a binary search tree); post-order is 1, 6, 3, 14, 10, 8; and level-order is 8, 3, 10, 1, 6, 14.
Key takeaways
Pre-order (node, left, right), in-order (left, node, right), and post-order (left, right, node) are depth-first traversals taking O(n) time and O(h) space. Pre-order suits copying; in-order yields sorted BST keys; post-order suits deletion and evaluation. Level-order uses a queue to go level by level. Iterative traversals use explicit stacks; Morris traversal uses O(1) space. Traversal orders produce prefix, infix, and postfix notation. Pre-order plus in-order rebuilds a tree uniquely. Many problems are traversals with per-node work.
Flashcard
Node, left, right
Check your understanding
Which traversal of a binary search tree outputs its keys in sorted order?