Binary Tree Traversals (Preorder, Inorder, Postorder, Level Order)

Trees are everywhere the data has a hierarchy: a filesystem, an org chart, the DOM of a web page, the parsed structure of an expression, a family tree. Whenever you need to touch every node of one, you face a small but consequential decision that is easy to gloss over: in what order? Get it right and problems that looked fiddly become one clean recursive function. Get it wrong and you compute a parent's answer before its children exist, which is nonsense. The four traversals are the four sensible answers to "what order," and the beautiful thing is how little separates them.

Here is the insight that turns four things you might memorize into one thing you understand. The three depth-first traversals run the exact same recursion, "handle me, recurse left, recurse right," and differ only in where you slot the word "handle" among those three moves. Handle the node before its children and you get preorder (root, left, right). Handle it between them and you get inorder (left, root, right). Handle it after both and you get postorder (left, right, root). One line moves; everything else is identical. Level order is the odd one out, a breadth-first sweep that visits the tree rank by rank using a queue, the same ring-by-ring walk as graph BFS.

One recursion, three positions, plus a queue

Watch the visit line slide down through left and right, and how the output reorders with it.

from collections import deque

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

def preorder(node):                                    # visit BEFORE children
    if not node: return []
    return [node.val] + preorder(node.left) + preorder(node.right)

def inorder(node):                                     # visit BETWEEN children
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

def postorder(node):                                   # visit AFTER children
    if not node: return []
    return postorder(node.left) + postorder(node.right) + [node.val]

def level_order(root):                                 # breadth-first, rank by rank
    if not root: return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder(root))     # [1, 2, 4, 5, 3]
print(inorder(root))      # [4, 2, 5, 1, 3]
print(postorder(root))    # [4, 5, 2, 3, 1]
print(level_order(root))  # [1, 2, 3, 4, 5]

Two of these orders are not arbitrary conveniences, they are forced by the problem. Inorder on a binary search tree emits values in sorted order, because "everything smaller, then me, then everything larger" is literally the sorted definition unrolled. And postorder is the order you are forced into whenever a node's answer depends on its children's answers, which is more common than it first sounds.

A binary tree with root 1, left child 2 whose children are 4 and 5, and right child 3, alongside its four traversal orders: preorder 1 2 4 5 3, inorder 4 2 5 1 3, postorder 4 5 2 3 1 and level order 1 2 3 4 5, which differ only in where the node is visited.

In the wild: how du measures a folder

Run du on a directory and it reports the total size of everything inside. Think about what that computation actually requires: a folder's size is its own overhead plus the sizes of all its children, so you cannot possibly know a folder's total until every child's total is already computed. That constraint has a name. It is postorder: process both children fully, then handle the parent.

def directory_size(node):                    # node.children is a list; leaves are files
    if not node.children:
        return node.size                     # a file: its own size
    total = node.size                        # the directory's own overhead
    for child in node.children:
        total += directory_size(child)       # children MUST finish first
    return total                             # only now can the parent report

This is postorder wearing work clothes (generalized past two children to any number), and the same shape solves a whole family: evaluating an expression tree needs both operand subtrees computed before you can apply the operator, deleting or freeing a tree must release children before the parent that points to them, and computing a tree's height or its node count is the same "aggregate the children, then myself." Whenever the answer flows upward from leaves to root, postorder is not a stylistic choice, it is the only order that works.

The trigger

You need to visit every node of a hierarchy, and the question is which order. "Sorted output from a BST" means inorder. "Aggregate something up from the leaves," evaluate, delete, or compute a subtree property, means postorder. "Copy, serialize, or explore top-down" means preorder. "Process level by level, or find the shallowest something" means level order. If the data is a tree and you are touching all of it, one of these four is the frame.

Where it shows up

  • Inorder: reading a BST in sorted order, validating BST ordering, finding the k-th smallest element.
  • Postorder: expression-tree evaluation, subtree sums and heights, safe deletion, most "answer depends on children" problems.
  • Preorder and level order: serializing or cloning a tree, printing an org chart, and level order for shortest-depth and per-level questions.

Where it bites

The recursive versions are clean but consume call stack proportional to the tree's height, so a deep or degenerate tree (a linked list in disguise) can blow the stack, at which point an explicit stack or Morris traversal earns its complexity. The concatenation style above (list + [val] + list) is readable but quietly O(n^2) in the worst case because each + copies; for large trees, append into a shared result list instead. And the ever-popular mistake: expecting inorder to give sorted output on a tree that is not a binary search tree, where it means nothing of the sort.

When it is the wrong tool

If your hierarchy is really a general graph with shared nodes or cycles, tree traversal will revisit or loop, and you need a graph traversal with a visited set. If you only need one specific node and the tree is a BST, do not traverse the whole thing, walk the search path in O(height). And if you are recomputing the same subtree's answer again and again across a larger problem, plain traversal is wasteful and you want to cache results, which is tree dynamic programming rather than a naive re-walk.

Its neighbors

These traversals are the tree special case of Graph Traversals: depth-first is DFS, level order is BFS, and the visited set simply disappears because a tree has no cycles. Postorder recursion is one short step from Backtracking and from tree Dynamic Programming. And they are the vehicle for Path Sum and Root-to-Leaf problems, which are traversals that carry state down as they descend.

References