Tree Traversals

Tree traversals visit every node in a defined order: pre-order, in-order, and post-order for depth, and level-order for breadth.

Four standard orders

A traversal is a systematic way to visit every node of a tree exactly once. For binary trees there are three depth-first orders, distinguished by when a node is visited relative to its children, plus one breadth-first order that sweeps level by level. Each order suits different tasks.

• Pre-order: node, then left subtree, then right — copies or serialises a tree
• In-order: left, node, right — yields sorted keys in a BST
• Post-order: left, right, then node — frees or evaluates children first
• Level-order: breadth-first by depth, using a queue

Depth-first traversals

The three depth-first orders are naturally recursive: each recurses into the left subtree and the right subtree, differing only in where it processes the current node. They all run in O(n) time and use stack space proportional to the tree height. An explicit stack gives the same orders iteratively when recursion depth is a concern.

def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

Breadth-first traversal

Level-order traversal visits all nodes at depth 0, then depth 1, and so on. It uses a queue: dequeue a node, process it, and enqueue its children. This is the tree specialisation of breadth-first search and is the way to find the shallowest node matching a condition.

Why the order matters

Choosing the right order is often the whole trick. In-order on a search tree recovers sorted data; post-order is required when a node's result depends on its children, as in evaluating an expression tree or computing subtree sizes; pre-order reproduces structure for serialisation. Morris traversal even achieves in-order in O(1) extra space by temporarily rewiring pointers.