Binary Tree Traversals: When Each One Actually Matters

Every tree problem boils down to traversal. You're either visiting nodes in a specific order to extract information, or you're modifying the tree as you go. The four main traversals exist because different problems need different visit orders. Knowing why each one matters is more useful than memorizing the code.

The Four Traversals

Given this tree:

        4
       / \
      2    6
     / \  / \
    1   3 5   7

Traversal	Order	Output
Inorder	left → root → right	1, 2, 3, 4, 5, 6, 7
Preorder	root → left → right	4, 2, 1, 3, 6, 5, 7
Postorder	left → right → root	1, 3, 2, 5, 7, 6, 4
Level-order	level by level (BFS)	4, 2, 6, 1, 3, 5, 7

Recursive Implementations

These are almost embarrassingly simple. The only difference is where you process the current node.

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

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

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

Three functions, identical structure, just moving one line around. That's the beauty of it.

Iterative Implementations

Interviews sometimes ask for iterative versions. These use an explicit stack instead of the call stack.

Iterative Inorder — this one's the most commonly asked:

def inorder_iterative(root):
    result = []
    stack = []
    current = root

while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

return result

The inner while drills down to the leftmost node. Then you pop, process, and move right. It mirrors exactly what the recursive version does — you're just managing the stack yourself.

Iterative Preorder — actually simpler than inorder:

def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]

while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:  # right first so left is processed first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

return result

Push right before left because the stack is LIFO — left will be popped (and processed) first.

Level-Order (BFS) — uses a queue, not a stack:

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])

while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

return result

The for _ in range(len(queue)) trick processes exactly one level per outer loop iteration. That's how you get the level-grouped output that many problems ask for.

When Each Traversal Matters

This is the part most articles skip, and it's the part that actually matters in interviews.

Inorder gives you BST nodes in sorted order. If the problem involves a BST and sorted output (kth smallest element, validate BST, convert BST to sorted linked list), inorder is your tool.

# Validate BST — inorder traversal must be strictly increasing
def is_valid_bst(root):
    prev = [float('-inf')]

def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

return inorder(root)

Preorder processes the root first, making it natural for serialization and tree construction. When you serialize a tree (convert to a string to save/transmit), preorder gives you a representation you can deserialize by reading left to right. Postorder processes children before the parent, which is what you need for deletion (delete children before the parent) and computing aggregate values (you need subtree results before you can compute the current node's answer). Problems like "height of tree," "diameter of tree," or "sum of all subtree values" are postorder patterns. Level-order is for anything that cares about depth or levels — minimum depth, maximum width, right-side view, zigzag traversal.

BST Operations

Since BST problems show up constantly, here are the essential operations.

Search — O(log n) average, O(n) worst case for a skewed tree:

def search(root, target):
    if not root:
        return None
    if target == root.val:
        return root
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Insert — same logic, but you create a new node when you hit a null:

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

Balanced vs Unbalanced

A balanced BST has O(log n) height. An unbalanced one degrades to O(n) — essentially a linked list. If you insert sorted data into a naive BST, you get a straight line to the right.

Self-balancing trees (AVL, Red-Black) fix this automatically. You don't need to implement them in interviews, but you should know they exist and why. When an interviewer asks about time complexity, the answer for BST operations is "O(log n) if balanced, O(n) worst case."

The Pattern to Remember

Most tree problems follow one template:

1. Handle the base case (null node)
2. Recurse on left and/or right subtrees
3. Combine results with the current node's value

The only thing that changes is when you process the current node (before, between, or after recursion) and what you compute. Once you internalize this, tree problems become very mechanical.

Practice these traversal patterns on actual trees at CodeUp — stepping through each traversal visually makes the recursive flow click much faster than reading code on a page.