Tree Traversals

There is only one natural way to traverse a linear structure: from start to end. In a tree, however, every node has at least two directions, and in which order to proceed is a decision.

This lesson defines the four basic traversal patterns. All four visit every node exactly once, so their cost is $O(n)$; where they differ is the order of the visit, and this order determines which problem a traversal can solve.

Three Depth Traversals

At a node in a binary tree there are three tasks: visiting the node itself, traversing the left subtree, and traversing the right subtree. Where the node’s visit falls within this triple gives the traversal its name.

• Preorder: Node first, then left, then right.
• Inorder: Left first, then node, then right.
• Postorder: Left first, then right, then node.

Notice that the left subtree is always traversed before the right; all three patterns share this common rule.

            (12)
           /    \
       (18)      (7)
      /   \        \
   (25)   (14)     (30)

Traversal	Order
Preorder	12, 18, 25, 14, 7, 30
Inorder	25, 18, 14, 12, 7, 30
Postorder	25, 14, 18, 30, 7, 12

class BinaryNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "BinaryNode | None" = None
        self.right: "BinaryNode | None" = None


def preorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        result.append(node.value)          # node first
        preorder(node.left, result)
        preorder(node.right, result)
    return result


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)          # node in the middle
        inorder(node.right, result)
    return result


def postorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.value)          # node last
    return result


root = BinaryNode(12)
root.left = BinaryNode(18); root.right = BinaryNode(7)
root.left.left = BinaryNode(25); root.left.right = BinaryNode(14)
root.right.right = BinaryNode(30)

print(preorder(root))       # [12, 18, 25, 14, 7, 30]
print(inorder(root))        # [25, 18, 14, 12, 7, 30]
print(postorder(root))      # [25, 14, 18, 30, 7, 12]

The only difference between the three functions is where the append line sits. This shows why the traversal patterns are considered members of the same family.

Which Traversal, Where

The difference in order determines which problems a traversal fits.

Preorder processes a node before its children. It suits copying a structure or serializing it: child nodes cannot be attached before the parent node exists. Printing a directory’s name before its contents when displaying a directory tree follows this same order.

Inorder gives elements in sorted order for binary search trees. This is the main result of the next lesson; for now it is enough to note that the order can be meaningful.

Postorder processes a node after its children. It is required for freeing a tree: if the parent node is freed before its children, access to the children is lost. For the same reason it is used in expression evaluation — an operator’s value cannot be found before its operands are computed. The postfix notation from the Stacks lesson is the postorder traversal of an expression tree.

Level order traverses the tree layer by layer, and is the subject of the next section.

Traversal with a Stack

The recursive form uses the call stack implicitly. The same traversal can also be written by keeping the stack explicitly; this is the application to trees of the “carrying the stack by hand” transformation from the Programming Fundamentals course.

def preorder_stack(root) -> list[int]:
    """Preorder traversal; an explicit stack instead of recursion."""
    if root is None:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right is not None:
            stack.append(node.right)        # right is pushed first
        if node.left is not None:
            stack.append(node.left)         # left is pushed second: popped first
    return result


print(preorder_stack(root))    # [12, 18, 25, 14, 7, 30]

Pushing the right child first is because a stack works in reverse order: last in, first out, so the left child is processed first. If this detail is skipped, the traversal goes right to left, and the result silently changes.

The rationale for using an explicit stack is the same as stated in the previous course: when depth grows with the data, the call stack can be exhausted. Production code that works with deep trees therefore often uses an explicit stack.

Level-Order Traversal

The fourth pattern proceeds along breadth, not depth: first the root, then every node at depth 1, then those at depth 2.

Its structure is the same as a depth traversal; the only difference is using a queue instead of a stack.

from collections import deque

def level_order(root) -> list[int]:
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()           # first in, first out
        result.append(node.value)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return result


def by_levels(root) -> list[list[int]]:
    """Returns each level in a separate list."""
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # current queue length = level width
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(level)
    return result


print(level_order(root))        # [12, 18, 7, 25, 14, 30]
print(by_levels(root))          # [[12], [18, 7], [25, 14, 30]]

The fact that using a queue instead of a stack completely changes the traversal pattern makes concrete why these two abstract types are defined separately. The same duality will repeat exactly between depth-first and breadth-first search in the graphs topic.

The loop inside by_levels determines the level boundary by reading the queue’s current length — newly added nodes are left for the next round.

Cost

Traversal is the basis of almost every operation defined on a tree: counting nodes, computing height, copying, comparing, and freeing — all of them are a specialized form of some traversal pattern.

All four traversals visit every node once: the time cost is $O(n)$.

Memory costs diverge. Depth traversals hold at most as many nodes on the stack as the tree’s height — $O(\log n)$ for a balanced tree, $O(n)$ for a degenerate one. Level-order traversal holds as many nodes in the queue as the width of the widest level; in a perfect tree, this is the node count of the last level, that is, $O(n)$.

Depth traversal uses less memory on wide, shallow trees; level traversal uses less on deep, narrow trees.

Summary

• Preorder, inorder, and postorder traversals differ only in when the node is visited; all three traverse the left subtree before the right.
• Preorder suits copying and serialization, postorder suits freeing and expression evaluation, inorder suits sorted output in search trees.
• Recursive traversal uses the call stack implicitly; the explicit-stack form is safe on deep trees.
• Using a queue instead of a stack makes the traversal level order.
• All four traversals have $O(n)$ time cost; memory cost depends on height for depth traversals and on the widest level for level-order traversal.

Next Step

Traversal covers the entire tree. To search for a value, however, it should not be necessary to traverse the whole tree; being able to choose the correct branch at every node is enough. The next lesson defines the ordering rule that makes this possible — the binary search tree.