Binary Tree Traversals: Inorder, Preorder, Postorder, Level-Order

A traversal is a recipe for visiting every node in a tree exactly once. Almost every binary-tree problem boils down to “pick the right traversal, then do the obvious thing at each node.” This post covers the four standard traversals — three depth-first, one breadth-first — in both recursive and iterative form.

The example tree

We’ll use this tree throughout:

         1
        / \
       2   3
      / \   \
     4   5   6

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

root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6)),
)

Depth-first traversals

The three DFS orders differ only in when you visit the current node relative to its children. The rest is identical.

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

A simple way to remember them: pre/in/post describes when you “say the node’s value” relative to recursing into its subtrees.

Preorder (Node, Left, Right)

def preorder(node, out=None):
    if out is None:
        out = []
    if node is None:
        return out
    out.append(node.value)
    preorder(node.left, out)
    preorder(node.right, out)
    return out

print(preorder(root))    # [1, 2, 4, 5, 3, 6]

Use preorder when you need to build or copy a tree top-down, or serialize it. The root comes first, then the left subtree’s serialization, then the right’s.

Inorder (Left, Node, Right)

def inorder(node, out=None):
    if out is None:
        out = []
    if node is None:
        return out
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)
    return out

print(inorder(root))    # [4, 2, 5, 1, 3, 6]

Inorder is the natural traversal for a Binary Search Tree — it visits nodes in sorted order. If someone asks you to print a BST’s values sorted, this is the one-liner.

Postorder (Left, Right, Node)

def postorder(node, out=None):
    if out is None:
        out = []
    if node is None:
        return out
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.value)
    return out

print(postorder(root))    # [4, 5, 2, 6, 3, 1]

Use postorder when you need to process children before the parent — typical when computing aggregates (sum, height, max depth) or freeing/deleting nodes.

Level-order traversal (BFS)

Instead of recursion, you process the tree one level at a time using a queue. This is breadth-first search applied to a tree.

from collections import deque

def level_order(root):
    if root is None:
        return []
    out = []
    q = deque([root])
    while q:
        node = q.popleft()
        out.append(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

print(level_order(root))    # [1, 2, 3, 4, 5, 6]

Use a collections.deque — its popleft is O(1), unlike a list’s pop(0).

Level-order grouped by level

A common variant returns a list of lists, one per level:

def level_order_grouped(root):
    if root is None:
        return []
    out = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.value)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

print(level_order_grouped(root))
# [[1], [2, 3], [4, 5, 6]]

The trick is snapshotting len(q) at the start of each level — that’s how many nodes belong to the current level, regardless of what you push next.

Iterative DFS

Recursive traversals are clean, but Python’s recursion limit (around 1000) bites on deep trees. Iterative versions use an explicit stack.

Iterative preorder

def preorder_iter(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.value)
        # push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

print(preorder_iter(root))    # [1, 2, 4, 5, 3, 6]

The key insight: a stack visits the most recently pushed node next, so to visit left before right you push right first.

Iterative inorder

def inorder_iter(root):
    out, stack = [], []
    node = root
    while node or stack:
        # walk left as far as possible, pushing as we go
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.value)
        node = node.right
    return out

print(inorder_iter(root))    # [4, 2, 5, 1, 3, 6]

This one takes a moment to internalize. The outer loop alternates between “drill left” and “pop and go right.”

Iterative postorder

Postorder is the trickiest iteratively. A clean trick: do a modified preorder (Node, Right, Left), then reverse:

def postorder_iter(root):
    if root is None:
        return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.value)
        if node.left:  stack.append(node.left)
        if node.right: stack.append(node.right)
    return out[::-1]

print(postorder_iter(root))    # [4, 5, 2, 6, 3, 1]

You’re essentially building Node-Right-Left order, then reversing it to get Left-Right-Node.

Complexity

All four traversals visit every node exactly once, so each is O(n) in time.

Space is where they differ:

• Recursive DFS uses O(h) stack space where h is the tree’s height. For a balanced tree h = log n; for a skewed tree h = n.
• Iterative DFS uses the same O(h) for the explicit stack.
• BFS uses O(w) for the queue, where w is the tree’s maximum width. For a perfect binary tree, the last level holds about n/2 nodes — so BFS can use O(n) space.

The takeaway: DFS is cheaper for very wide trees; BFS is cheaper for very deep trees.

Which traversal when?

A rough decision guide:

Situation	Traversal
Sort a BST’s values	Inorder
Copy or serialize a tree	Preorder
Compute heights/sums bottom-up	Postorder
Delete/free nodes	Postorder
Find the shortest path in #edges	Level-order (BFS)
Level-by-level processing	Level-order
Find depth of a specific value	Level-order
Validate a BST	Inorder (or recursive bounds)

When in doubt for tree problems, start with the recursive version of the right DFS. If you hit recursion limits or need explicit level information, switch to iterative or BFS.

A worked example: validating a BST with inorder

A BST’s inorder traversal must produce strictly increasing values. That gives a clean validator:

def is_valid_bst(root):
    prev = [None]    # use a list so the inner function can mutate it
    def walk(node):
        if node is None:
            return True
        if not walk(node.left):
            return False
        if prev[0] is not None and node.value <= prev[0]:
            return False
        prev[0] = node.value
        return walk(node.right)
    return walk(root)

# A valid BST
bst = TreeNode(5,
    TreeNode(3, TreeNode(1), TreeNode(4)),
    TreeNode(8, TreeNode(7), TreeNode(9)),
)
print(is_valid_bst(bst))    # True

# A broken BST (7 is in the left subtree of 5)
broken = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(7)), TreeNode(8))
print(is_valid_bst(broken))    # False

The whole idea: walk inorder, and the moment you see a value that isn’t strictly larger than the previous one, the tree isn’t a BST.

Recap

You now know:

• DFS has three flavours — preorder, inorder, postorder — distinguished by when you visit the node
• Inorder on a BST yields sorted output; preorder is good for serializing; postorder is good for aggregates
• Level-order (BFS) walks the tree level-by-level using a deque
• Each traversal has a clean recursive form and a useful iterative form using a stack or queue
• All are O(n) time; DFS uses O(h) space, BFS up to O(n) for very wide trees

Next steps

The next post applies these traversals to eight classic interview problems — max depth, same tree, invert, symmetric, path sum, lowest common ancestor, validate BST, and serialize/deserialize. Each is a short variation on the patterns you just learned.

→ Next: Binary Trees Practice Problems

Questions or feedback? Email codeloomdevv@gmail.com.