Binary tree traversal explained: preorder, inorder, postorder and level order

Why traversal order matters

A tree has no single natural order, so algorithms choose the one that fits the task. Inorder traversal of a binary search tree yields the keys in sorted order. Preorder visits a parent before its children, which is what you need to copy a tree or write it out so it can be rebuilt. Postorder visits children before the parent, which is what you need to delete a tree, compute folder sizes, or evaluate an expression tree. Level order finds the shallowest node first and prints a tree row by row.

The four orders on one example

We use this tree: root 1 with children 2 and 3; node 2 has children 4 and 5; node 3 has a right child 6.

        1
       / \
      2   3
     / \   \
    4   5   6

A simple way to remember the first three: the name says where the node goes. Pre means before both subtrees, in means between them, post means after them. The left subtree is always visited before the right one.

Recursive implementations

The recursive versions mirror the definitions directly. Each function visits the node at a different line.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

Iterative preorder and inorder with a stack

Recursion uses the call stack. To avoid recursion limits on deep trees, manage the stack yourself. For preorder, pop a node, visit it, then push the right child before the left child so that the left one is processed first.

For inorder, walk left as far as possible, pushing nodes on the way. When you cannot go further left, pop a node, visit it, and move to its right child.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

Iterative postorder and level order

Iterative postorder is the trickiest. One clean approach uses a flag: push each node twice, the second time marked as ready to visit after its children. Level order uses a queue instead of a stack; processing the queue one level at a time also tells you the depth of each node.

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

Another common trick for postorder: run a modified preorder (node, right, left) and reverse the result.

Time and space complexity

Here n is the number of nodes, h the height and w the maximum width. For a balanced tree h is about log2(n) and w can be about n/2; for a chain-shaped tree h is n and w is 1.

Common mistakes

• Pushing the left child before the right child in iterative preorder. A stack is LIFO, so the child you want first must be pushed last.
• Forgetting the empty tree: every function should return an empty result for root is None.
• Using a list with pop(0) as the queue in level order. It is O(n) per pop; use collections.deque.
• Relying on recursion for very deep trees. Python stops at its recursion limit (about 1000 by default) with RecursionError.
• Expecting a single traversal to identify a tree. Preorder alone is ambiguous; preorder plus inorder (with distinct values) is enough to rebuild it.

When to use which traversal

Preorder, inorder and postorder are all forms of depth-first search; level order is breadth-first search applied to a tree. The same ideas extend to general graphs, where you also need a set of visited nodes.