Lesson 13 · Non-linear structures

Tree Traversals

Tree traversals dictate the exact sequence in which every node in a tree is visited, serving as the blueprint for serialization and evaluation.

One Recursion, Three Placements

A traversal visits every node in a tree exactly once. For a linear structure there is only one sensible order; a tree branches, so the order has to be chosen — and the choice is what distinguishes the methods.

The three depth-first traversals are not three algorithms. They are one recursion with the visit placed at three different points relative to the two recursive calls. Recognising this collapses a lot of memorisation.

Pre-order: visit the node, then recurse left, then recurse right — node first. In-order: recurse left, visit the node, recurse right — node between. Post-order: recurse left, recurse right, then visit — node last.

The naming is consistent and worth pointing out: the prefix describes when the node itself is handled relative to its subtrees. Left always precedes right in all three; the mirrored variants exist but are rarely used.

All three are O(n) in time, since every node is visited once and does O(1) work. All three use O(h) space for the call stack, where h is the height — O(log n) on a balanced tree and O(n) on a degenerate one, which is the case that overflows the stack and forces an iterative rewrite.

One recursion; the visit moves relative to the two calls
Pre-order visits first, in-order between, post-order last
The prefix names when the node is handled, not the children
O(n) time, O(h) stack space for all three

What Each Order Is For

The orders are not interchangeable — each exists because some task requires exactly that sequence.

Pre-order processes a parent before its children, which is what you need when the children's handling depends on the parent already existing. Copying a tree must create a node before attaching its children to it. Serialising a tree must write the parent first so a reader can rebuild top-down. Printing a directory tree or an outline uses pre-order for the same reason — the heading precedes what it contains.

Post-order processes children before the parent, which is what you need when the parent's result depends on its children. Freeing a tree must delete children first, or the pointers to them are lost. Computing a height or a size needs both subtree values before combining them. Evaluating an expression tree must have both operand results before applying the operator. Deleting a directory requires emptying it first.

That contrast is the useful summary: pre-order builds, post-order collapses. Any bottom-up computation over a tree — heights, diameters, subtree sums — is a post-order traversal, and any top-down one is pre-order.

In-order is the one specific to binary trees, since it depends on there being exactly two sides to sit between. On a binary search tree it emits the keys in ascending sorted order, which follows directly from the invariant: everything left is smaller, everything right is larger.

That makes it the natural way to extract sorted output in O(n) without sorting, to validate a BST by checking each key exceeds the previous, and to find the kth smallest element by counting visits. On a tree that is not a search tree, in-order has no particular meaning.

When to use each order
Order	Sequence	Use it for
Pre-order	Node, left, right	Copying, serialising, top-down computation
In-order	Left, node, right	Sorted output from a BST, validation, kth smallest
Post-order	Left, right, node	Freeing, heights and sizes, expression evaluation
Level-order	By depth, using a queue	Depth questions, shortest path, per-level output

Pre-order builds top-down; post-order collapses bottom-up
Copy and serialise with pre-order; free and compute heights with post-order
In-order on a BST gives sorted keys — the basis of validation
In-order carries no meaning on a non-search tree

Level Order and the Queue

Level-order traversal visits all nodes at depth 0, then all at depth 1, and so on. It is breadth-first search applied to a tree, and it is structurally different from the other three: it uses a queue, not recursion.

The loop is short. Enqueue the root; while the queue is not empty, dequeue a node, visit it, and enqueue its non-null children. FIFO order is what guarantees that every node at one depth is processed before any node at the next.

Producing per-level output — a list of lists rather than a flat sequence — requires one addition that is worth knowing precisely: record the queue's size at the start of each round, then process exactly that many nodes. Those are exactly the nodes of the current level, since all of them were enqueued before any of their children. Without this the levels blur together and the grouping is lost.

It answers the questions the depth-first orders answer awkwardly: the height of a tree by counting rounds, the rightmost node of each level for the classic right-side-view problem, whether a tree is complete, and the shortest path from the root, since the first time a node is dequeued it is at its minimum depth.

The space characteristics invert. Depth-first uses O(h) — small on wide, shallow trees. Level-order uses O(w) where w is the maximum width, which for a perfect tree is n/2 at the last level. So a wide tree favours depth-first, a deep tree favours level-order, and the choice on a large tree can be about memory rather than about the output order.

A queue, not recursion — FIFO enforces the level ordering
Capture the queue size per round to group nodes by level
Answers height, per-level views, and shortest depth
O(width) space — the opposite trade from depth-first's O(height)

Key reference

Terms, operations, and practical uses

Depth-First Strategies

Pre-orderProcess the current node, then traverse left, then traverse right. Excellent for deep-copying or serializing trees.
In-orderTraverse left, process the node, then traverse right. Used primarily to extract sorted data from a BST.
Post-orderTraverse left, traverse right, then process the node. Required for deleting trees or aggregating subtree values (like heights).

Breadth-First Strategies

Level-orderProcesses all nodes at depth 0, then depth 1, etc. Implemented using a Queue instead of the call stack.
Right-Side ViewA variation of level-order traversal where only the last processed node of each depth level is captured.
Shortest PathIn unweighted tree structures, level-order traversal inherently discovers the shortest path from the root to any target.

Implementation Details

Call StackRecursive DFS relies on the system call stack, making it vulnerable to StackOverflow errors on heavily degenerate trees.
Iterative DFSDFS can be performed iteratively by manually pushing nodes onto a Stack, resolving recursion limit issues.
Morris TraversalAn advanced O(N) time traversal that achieves O(1) space by temporarily modifying null leaf pointers to route back to ancestors.

Implementation

Traverse a binary tree in inorder

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

visited = []
def inorder(node):
    if not node:
        return
    inorder(node.left)
    visited.append(node.val)
    inorder(node.right)

root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
inorder(root)
print('Inorder: ' + ' '.join(str(v) for v in visited))

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {
    }
};
void inorder(TreeNode* node, vector<int>& visited) {
    if (!node) return;
    inorder(node->left, visited);
    visited.push_back(node->val);
    inorder(node->right, visited);
}
int main() {
    TreeNode* root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    vector<int> visited;
    inorder(root, visited);
    cout << "Inorder:";
    for (int v : visited) cout << ' ' << v;
    cout << '\n';
}

import java.util.*;
public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) {
            val = x;
        }
        TreeNode(int x, TreeNode l, TreeNode r) {
            val = x;
            left = l;
            right = r;
        }
    }
    static void inorder(TreeNode node, List<Integer> visited) {
        if (node == null) return;
        inorder(node.left, visited);
        visited.add(node.val);
        inorder(node.right, visited);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
        new TreeNode(2, new TreeNode(4), new TreeNode(5)),
        new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        List<Integer> visited = new ArrayList<>();
        inorder(root, visited);
        StringBuilder sb = new StringBuilder("Inorder:");
        for (int v : visited) sb.append(' ').append(v);
        System.out.println(sb);
    }
}

Watch it run

Step through it

Running on seven-node tree, root 1

Output

Read all 15 Steps

Start Call inorder(1). Nothing is printed until we reach the deepest left node.
Go left inorder(2). Still descending — a node is only printed after its whole left subtree.
Go left inorder(4). Node 4 has no children, so this is the deepest point of this branch.
Visit 4 Left of 4 is null, so 4 is printed and the frame returns.
Visit 2 Back in 2. Its left subtree is finished, so 2 prints now.
Go right inorder(5), the right child of 2.
Visit 5 5 is a leaf: print it and return, finishing the whole left subtree of 1.
Visit 1 Control is back at the root. Its left subtree is done, so the root prints in the middle.
Go right inorder(3). The right subtree repeats the same pattern.
Go left inorder(6), the deepest left node of the right subtree.
Visit 6 6 is a leaf: print and return.
Visit 3 3's left subtree is complete, so 3 prints.
Go right inorder(7), the last node.
Visit 7 7 is a leaf: print it.
Done Every frame has returned. Inorder printed the left subtree, the node, then the right subtree at every level.

Iterative Forms and Reconstruction

Recursion consumes stack frames, so a degenerate tree of a million nodes will overflow. The iterative forms replace the implicit stack with an explicit one.

Pre-order is the easiest: push the root; pop a node, visit it, then push its right child first and left second so the left is popped first. The reversed push order is the detail people get wrong.

In-order needs a different shape, since a node cannot be visited until its left subtree is exhausted. Descend leftward pushing every node; when null is reached, pop, visit, and move to the popped node's right child, then repeat. The stack holds the ancestors still awaiting their visit.

Post-order is the awkward one, because the node must be visited after both children — so a popped node cannot immediately be visited. The clean trick is to run a modified pre-order as node-right-left, then reverse the result, which yields left-right-node. The direct two-stack or last-visited-pointer methods work too but are fiddlier.

A related idea worth knowing: Morris traversal achieves in-order in O(1) space with no stack at all, by temporarily rewiring the rightmost node of each left subtree to point back at the current node, then undoing the link on the way through. It mutates the tree during traversal, which rules it out for concurrent access, but it is the answer when constant space is demanded.

Reconstruction appears often, and the rule is worth stating precisely. Pre-order plus in-order determines a binary tree uniquely: pre-order gives the root, in-order locates it and splits the remaining keys into left and right subtrees, and recursion does the rest. Post-order plus in-order works the same way, taking the root from the end.

But pre-order plus post-order does not determine the tree, because neither tells you where a subtree ends when a node has only one child — the tree is ambiguous. The general principle is that in-order supplies the split point, so it is the traversal you cannot do without. The exception is a full binary tree, where every node has 0 or 2 children, and pre-order with post-order becomes sufficient.

Iterative pre-order pushes right before left
Post-order is easiest as reversed node-right-left
Morris traversal gives in-order in O(1) space by rewiring temporarily
Reconstruction needs in-order; pre plus post is ambiguous