Binary Tree Traversal: Preorder, Inorder and Postorder

Preorder, inorder and postorder are usually taught as three algorithms to memorise. They are one algorithm. Every depth-first traversal visits the left and right subtrees; the only choice is when the node itself is handled: before both, between them, or after both. Once you see that, the real interview questions, the iterative versions and "which order does this problem need?", become easy to reason about.

The problem it solves

A tree has no single natural order. An array is read left to right; a tree branches, so "visit every node" needs a rule for which branch comes first and where the parent fits in. Depth-first traversals go as deep as possible down one branch before backing up, and differ only in where the parent is emitted:

• Preorder: node, left subtree, right subtree.
• Inorder: left subtree, node, right subtree.
• Postorder: left subtree, right subtree, node.

Level order, the breadth-first alternative, reads the tree row by row with a queue and is a different tool; it is covered in binary tree level order traversal.

The intuition

Write the recursive function once, with three lines: recurse left, recurse right, and handle the node. Moving the "handle the node" line is the entire difference between the three orders.

What each placement means is what matters in interviews:

• Preorder sees the parent before its children. Anything that must exist first, such as copying a node, serialising it, or passing a value down, is preorder work.
• Inorder puts the parent between its subtrees. In a binary search tree everything on the left is smaller and everything on the right is larger, so inorder emits the values sorted. That fact is behind validating a BST and finding the k-th smallest value.
• Postorder sees the parent after both children. Anything computed from the children's answers, such as height, size, subtree sums or deleting a tree safely, is postorder work.

All three visit each node once. The recursion uses a call stack as deep as the tree is tall; the iterative versions replace it with an explicit one.

Watch it run

The animation uses the smallest tree where the orders differ: B with children A and C. Preorder first: same three nodes, same recursion, and only the line that handles the node itself moves. Preorder handles the node before either subtree, so B is emitted first and the children afterwards: then the left subtree, A, then the right, C. Preorder gives ['B', 'A', 'C']. Inorder goes left first, so the whole left subtree is emitted before the node: A. The node is handled between its two subtrees, so B lands in the middle, and the right subtree comes last: C. On a BST this order is sorted, and inorder gives ['A', 'B', 'C']. Postorder handles the node after both subtrees, which is why it suits totals: children finish first. Both children, A and C, are emitted before the parent gets its turn, and postorder gives ['A', 'C', 'B']. Three orders, one traversal, and every version touches every node once: O(n).

The code

The three recursive versions, identical except for where n.val sits:

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

def preorder(n):
    return [] if not n else [n.val] + preorder(n.left) + preorder(n.right)

def inorder(n):
    return [] if not n else inorder(n.left) + [n.val] + inorder(n.right)

def postorder(n):
    return [] if not n else postorder(n.left) + postorder(n.right) + [n.val]

root = Node("B", Node("A"), Node("C"))
print(preorder(root))    # ['B', 'A', 'C']   node first
print(inorder(root))     # ['A', 'B', 'C']   node in the middle
print(postorder(root))   # ['A', 'C', 'B']   node last

The iterative versions, the usual follow-up. Preorder pops a node and pushes the right child before the left, so the left comes off first. Inorder runs as far left as it can, then emits and turns right. Postorder is the cheapest trick: a preorder that goes node, right, left, reversed at the end:

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        n = stack.pop()
        out.append(n.val)
        if n.right:
            stack.append(n.right)        # pushed first, so popped after the left
        if n.left:
            stack.append(n.left)
    return out

def inorder_iter(root):
    out, stack, n = [], [], root
    while stack or n:
        while n:                         # run as far left as possible
            stack.append(n)
            n = n.left
        n = stack.pop()
        out.append(n.val)                # everything to its left is done
        n = n.right
    return out

def postorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        n = stack.pop()
        out.append(n.val)                # node, right, left ...
        if n.left:
            stack.append(n.left)
        if n.right:
            stack.append(n.right)
    return out[::-1]                     # ... reversed is left, right, node

tree = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
print(preorder_iter(tree))    # [4, 2, 1, 3, 6, 5, 7]
print(inorder_iter(tree))     # [1, 2, 3, 4, 5, 6, 7]   a BST, so sorted
print(postorder_iter(tree))   # [1, 3, 2, 5, 7, 6, 4]

Two small functions that show why the order matters. Size needs the children's answers first, so it is postorder; a copy needs the parent to exist first, so it is preorder:

def size(n):
    return 0 if not n else size(n.left) + size(n.right) + 1   # postorder: children first

def copy(n):
    return None if not n else Node(n.val, copy(n.left), copy(n.right))   # preorder: parent first

print(size(tree), inorder(copy(tree)) == inorder(tree))   # 7 True

The iterative versions against the recursive ones on 3,000 random binary search trees, with inorder also checked against a plain sort of the values:

import random

def random_tree(values):
    if not values:
        return None
    i = random.randrange(len(values))
    return Node(values[i], random_tree(values[:i]), random_tree(values[i + 1:]))

random.seed(21)
ok = True
for _ in range(3000):
    vals = random.sample(range(100), random.randint(0, 12))
    t = random_tree(sorted(vals))        # built from sorted values: a BST
    ok &= preorder_iter(t) == preorder(t)
    ok &= inorder_iter(t) == inorder(t) == sorted(vals)
    ok &= postorder_iter(t) == postorder(t)
    ok &= size(t) == len(vals)
print(ok)                     # True

The complexity

• Time: O(n) for every order, recursive or iterative, since each node is pushed and popped once. The list-concatenating versions above are for reading; they copy lists and can cost O(n²) on a long chain, so production code appends to one shared list.
• Space: O(h) for the recursion or the explicit stack, where h is the height. That is O(log n) for a balanced tree and O(n) for a degenerate one that is really a linked list. Morris traversal gets to O(1) by temporarily rewiring pointers, which is worth naming but rarely worth writing.

Where it goes wrong

• Pushing children in the wrong order. In iterative preorder the right child goes on the stack first; push left first and you get node, right, left.
• Treating the reversed trick as a true postorder. It gives the right output, but only after building the whole list, so it cannot stream results or stop early.
• Assuming inorder is sorted on any tree. It is sorted only when the tree is a binary search tree; that is exactly what makes it a validity test.
• Deep recursion on a skewed tree. Python's default recursion limit is about 1,000 frames, so a 10,000-node chain needs the iterative version.
• Forgetting the empty tree. Every version should return an empty list for None, which is why the base case comes first.

When it shows up in interviews

Traversals are the building block rather than the question. Validating a BST is inorder with a running previous value. Serialising a tree is preorder with null markers. Rebuilding a tree from preorder and inorder uses one order to find roots and the other to split subtrees, and the diameter of a binary tree is a postorder pass. The iterative inorder is also asked on its own, often as "implement a BST iterator".

How to say it in an interview

"All three are the same depth-first recursion; the only difference is when I handle the node. Preorder handles it before the subtrees, so I use it when the parent has to exist first, such as copying or serialising. Inorder handles it between them, so on a BST it gives the values in sorted order. Postorder handles it after both, so I use it whenever the parent's answer depends on the children's, like height or subtree sums. Each is O(n) time and O(h) space. If the tree can be deep, I replace the call stack with an explicit one: pop and push right then left for preorder, run left then emit and turn right for inorder."