Tree Traversals

A binary tree is either empty or a node with a key, a left subtree, and a right subtree (each itself a binary tree). A traversal is an algorithm that visits every node of the tree exactly once, producing a linear sequence from the tree's recursive structure. Because a node has three "parts" — itself, its left subtree, its right subtree — there are three natural depth-first orders depending on when the node itself is emitted relative to the two recursive subtree visits.

Preorder visits the node first, then recursively traverses the left subtree, then the right: root, left, right (often written N-L-R). Inorder visits left, then the node, then right (L-N-R). Postorder visits left, then right, then the node last (L-R-N). All three are depth-first: they plunge to a leaf before backtracking, and they can be implemented either with the language's own call stack (recursion) or an explicit stack that simulates it.

Level-order traversal (also called breadth-first traversal) abandons the root/left/right framing entirely. It visits nodes in order of increasing depth — all nodes at depth 0, then depth 1, then depth 2, and so on — using a Queues and Deques to remember which nodes to visit next, rather than a stack. Level-order has no natural recursive formulation; it is inherently iterative. Together these four orders form the complete basic toolkit: three ways to linearize a tree depth-first, one way breadth-first.

Recursive depth-first traversals. Each of the three DFS orders differs only in where the "visit(node)" line sits relative to the two recursive calls. ``` PREORDER(node): if node is null: return visit(node) PREORDER(node.left) PREORDER(node.right) INORDER(node): if node is null: return INORDER(node.left) visit(node) INORDER(node.right) POSTORDER(node): if node is null: return POSTORDER(node.left) POSTORDER(node.right) visit(node) ``` The base case — `node is null` — terminates recursion at every leaf's non-existent child. Every internal call makes exactly two recursive calls, one per child, so the recursion structure exactly mirrors the tree's own shape.

Iterative preorder simulates recursion with an explicit stack. Because preorder visits the node before its children, we can push the node, pop it, visit it immediately, then push right before left (so left is popped and processed first): ``` ITERATIVE-PREORDER(root): if root is null: return stack = new Stack() stack.push(root) while stack is not empty: node = stack.pop() visit(node) if node.right is not null: stack.push(node.right) if node.left is not null: stack.push(node.left) ```

Iterative inorder is trickier because a node is visited only after its entire left subtree is done. The standard technique walks left as far as possible, pushing every node along the way, then backtracks: ``` ITERATIVE-INORDER(root): stack = new Stack() node = root while node is not null or stack is not empty: while node is not null: // descend left, remembering the path stack.push(node) node = node.left node = stack.pop() // leftmost unvisited ancestor visit(node) node = node.right // now explore its right subtree ```

Iterative postorder is the hardest of the three because a node is visited last, after both children — so we must know we have already finished the right subtree before visiting. One clean method uses two stacks: ``` ITERATIVE-POSTORDER(root): if root is null: return stack1 = new Stack(); stack2 = new Stack() stack1.push(root) while stack1 is not empty: node = stack1.pop() stack2.push(node) if node.left is not null: stack1.push(node.left) if node.right is not null: stack1.push(node.right) while stack2 is not empty: visit(stack2.pop()) // stack2 unwinds in L-R-N order ``` This works because `stack1` produces a root, right, left order (mirror of preorder with children pushed in the opposite order); reversing that entire sequence — which is exactly what popping `stack2` does — yields left, right, root, i.e. postorder.

Level-order traversal uses a queue instead of a stack, since we want to process nodes in the order they were discovered (FIFO), not the reverse (LIFO): ``` LEVEL-ORDER(root): if root is null: return queue = new Queue() queue.enqueue(root) while queue is not empty: node = queue.dequeue() visit(node) if node.left is not null: queue.enqueue(node.left) if node.right is not null: queue.enqueue(node.right) ``` Each node enqueues its children right after being dequeued itself, so all depth-$d$ nodes are enqueued before any depth-$(d{+}1)$ node, guaranteeing breadth-first order.

Time complexity — $\Theta(n)$ for all four traversals, where $n$ is the number of nodes. Every traversal visits each node exactly once and does $O(1)$ work per node beyond the recursive/queueing overhead (one `visit` call, at most two pushes/enqueues, at most one pop/dequeue). Summing $O(1)$ work over $n$ nodes gives $\Theta(n)$ total. This is asymptotically optimal: any algorithm that must output all $n$ node values needs at least $\Omega(n)$ time just to write the output. A short inductive argument makes the recursive correctness precise. Claim: `PREORDER(node)` visits every node in the subtree rooted at `node` exactly once, in the order root-then-left-subtree-then-right-subtree.

• Base case: if `node` is null, the subtree is empty and zero nodes are visited — vacuously correct.
• Inductive step: assume the claim holds for smaller subtrees (fewer nodes) — namely for `node.left` and `node.right`. The algorithm visits `node` itself once, then by the inductive hypothesis `PREORDER(node.left)` visits every node in the left subtree exactly once in preorder, then likewise for the right subtree. No node is shared between `{node}`, the left subtree, and the right subtree (they partition the node set of a tree by definition), so every node in `node`'s subtree is visited exactly once, in root/left/right order.

The identical argument, with the `visit` call relocated, proves inorder and postorder correct. This is structural induction on subtree size — the standard proof technique for any recursive tree algorithm. For level-order, correctness follows from a queue invariant: at the start of each iteration, the queue contains exactly the not-yet-visited nodes at depth $d$ followed by all discovered nodes at depth $d+1$, for some $d$ that is non-decreasing over time. Since the queue is FIFO, all depth-$d$ entries are dequeued (and their depth-$(d{+}1)$ children enqueued) before any depth-$(d{+}1)$ node is dequeued. Hence nodes are visited in strictly non-decreasing depth order, which is the definition of level-order.

Space complexity.

Here $h$ is the tree's height and $w$ its maximum width. In the worst case (a completely unbalanced, "linked-list-shaped" tree) $h = n$, so DFS traversals cost $O(n)$ space; in a balanced tree $h = O(\log n)$. Level-order's queue can hold up to $O(n)$ nodes in the worst case too — for instance in a "bushy" tree where the bottom level alone has close to $n/2$ nodes. So in the worst case, all four traversals use $O(n)$ auxiliary space, but recursive/stack-based DFS is far cheaper ($O(\log n)$) on balanced trees, while level-order's cost tracks the tree's width rather than its height.

Tradeoffs. Recursive code is short and obviously correct by the induction above, but risks stack overflow on very deep, unbalanced trees (a real concern for adversarially built or degenerate trees) and carries function-call overhead. Iterative versions avoid call-stack limits and overhead but are more error-prone to write correctly — especially iterative postorder, which is the classic "hard" traversal to implement from scratch. Level-order traversal is the only order that reveals depth information cheaply and is essential when "closest nodes first" matters, e.g., shortest-path-like queries on trees.

Use the tree from the figure. Node keys and structure: ``` F / \ B G / \ \ A D I / \ C E ```

Preorder (N, L, R), recursive call trace — the sequence of `visit` calls in order:

Output: F B A D C E G I

Inorder (L, N, R) descends fully left before visiting anything: Output: A B C D E F G I — notice this is alphabetically sorted. That is not a coincidence for this example; it is the defining property exploited by Binary Search Trees, where inorder traversal always yields keys in sorted order regardless of shape.

Postorder (L, R, N), traced via the two-stack iterative method:

Popping stack2 (LIFO) reverses this to: A C E D B I G F — matching left-right-root order exactly.

Level-order, tracing the queue:

Output: F B G A D I C E — exactly depth 0, then depth 1, then depth 2 (A, D, I), then depth 3 (C, E). This matches the figure's annotation.

Tree traversal as formal technique emerged alongside the broader development of graph and tree algorithms in the early era of computer science, when trees became the standard model for hierarchical data — expression parsing, file systems, and search structures. The recursive formulations trace directly to the recursive definition of trees themselves and to early work connecting recursion to stack-based computation.

Compilers and interpreters parse source code into an abstract syntax tree and evaluate it in postorder: operands must be computed before the operator that combines them, exactly matching left-right-root order. File system utilities (like `du` or recursive directory printers) use preorder to print a directory before its contents, or postorder to compute sizes bottom-up before printing totals (this is how `du` accumulates directory sizes). Database indexes and <a class="wiki-link" href="/wiki/cs-algo-binary-search-trees" data-track="wiki_article.body.wiki_link">Binary Search Trees</a> rely on inorder traversal to produce sorted output for range queries — this is the mechanism behind `SELECT ... ORDER BY` on an indexed column in some database engines. Serialization formats (JSON, XML, protocol buffers) are built and parsed using preorder-like recursive descent, writing structure before content.

Level-order traversal underlies breadth-first search generalizations used in network routing (shortest hop-count paths), web crawlers (visiting pages by link-distance from a seed), and UI rendering engines that lay out widget trees level by level. Garbage collectors in managed-memory runtimes (JVM, .NET, V8) traverse object-reference graphs — trees in the common case, general graphs otherwise — using traversal strategies directly descended from these four patterns to mark reachable objects. Every balanced-tree data structure (AVL trees, red-black trees, B-trees) inherits these exact traversal algorithms unchanged; the traversal mechanics do not care how the tree is kept balanced, only that it is a binary (or, with minor generalization, $k$-ary) tree.

Ask the tutor: How would iterative postorder traversal change if the tree were general (k-ary) instead of binary?