Tree Traversals · Data Structures & Algorithms

There are only three places to do the work in a depth-first traversal: before you touch the children, between them, or after both return. That single choice is what separates preorder, inorder, and postorder. Get it right and the solution is five clean lines; get it wrong and you spend the whole problem fighting the recursion, threading state through parameters that should never have existed. Inorder carries the one property worth memorizing cold: on a BST, it hands you the values in sorted order.

The Three Traversals: Every DFS processes nodes in one of three orders:
- Preorder: Process node, then children (root → left → right)
- Inorder: Process left, then node, then right (left → root → right)
- Postorder: Process children, then node (left → right → root)

The name tells you WHEN you process the current node relative to its children.

The Same Tree, Three Orders

Trace all three traversals on the same tree:

Preorder: 1 → 2 → 4 → 5 → 3 (process, then recurse)

Inorder: 4 → 2 → 5 → 1 → 3 (left, process, right)

Postorder: 4 → 5 → 2 → 3 → 1 (recurse, then process)

Preorder: Top-Down Processing

Preorder does the node's work before it recurses, so the parent always acts first. That ordering is what you want whenever information flows downward, like reading a table of contents where the chapter title comes before its sections.

Cloning a tree, serializing its structure, carrying a running path from root to leaf: in each of these the parent has to establish something the children will read. Preorder guarantees the parent runs in time to set it up.

python

def preorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # Process BEFORE recursing
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return result

Use Preorder when:
- You need to process parents before children
- You're copying/cloning a tree
- You're serializing a tree (save structure)
- You need to pass information DOWN the tree

Inorder: Sorted Order for BST

Inorder slots the node's work between the two recursive calls, and on a binary search tree that placement is quietly powerful. Every left descendant is smaller, every right descendant is larger, so visiting the left subtree, then the node, then the right subtree walks the values in increasing order. That isn't a coincidence you have to memorize; it falls straight out of the BST invariant.

Whenever a problem leans on BST ordering, whether you're validating one or pulling the kth smallest, reach for inorder before anything else.

python

def inorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # First left subtree
        result.append(node.val)  # Process BETWEEN children
        dfs(node.right)          # Then right subtree
    
    dfs(root)
    return result
# BST [2,3,4,5,7] → Inorder: [2,3,4,5,7] - sorted!

Use Inorder when:
- You need BST nodes in sorted order
- You're validating a BST
- You're finding kth smallest/largest in BST
- The problem involves "between" relationships

Postorder: Bottom-Up Processing

Postorder runs the node's work after both children return, which makes it the workhorse of tree problems. Most computations simply can't finish at the parent until the children report back.

Height? Take the max of the two child heights, add one. Balance? Compare those same two heights. The parent has no answer to give until it hears from below, and that upward flow of results is exactly what postorder hands you.

python

def postorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # First left subtree
        dfs(node.right)          # Then right subtree
        result.append(node.val)  # Process AFTER recursing
    
    dfs(root)
    return result

Use Postorder when:
- You need children's results to compute parent's result
- Calculating tree height, diameter, balance
- Deleting a tree (delete children before parent)
- Any "aggregate up" computation

Visualizing the Difference

Trace all three on one tree and watch which node gets appended to the output at each step. The tree never changes shape; only the moment of processing moves.

Preorder: process BEFORE recursing

start

Output: []

The Pattern: Where You Put the Work

All three traversals use the same structure. The only difference is WHERE you do the work:

python

def dfs(node):
    if not node:
        return
    
    # === PREORDER WORK HERE ===
    # (before any recursion)
    
    dfs(node.left)
    
    # === INORDER WORK HERE ===
    # (between left and right)
    
    dfs(node.right)
    
    # === POSTORDER WORK HERE ===
    # (after all recursion)

Real Example: Max Depth

Max depth is postorder in its purest form. Ask how tall the tree is and you instinctively check both subtrees, keep the taller one, and add one for the current node. You genuinely cannot answer without your children's answers first.

The recursion asks for a small leap of faith: trust that max_depth(root.left) returns the correct depth of the entire left subtree, however tangled it is underneath. Don't trace how. Take the number, add one, take the max, and return.

python

def max_depth(root):
    if not root:
        return 0                             # Base case: empty tree
    left_depth = max_depth(root.left)        # Get left subtree depth
    right_depth = max_depth(root.right)      # Get right subtree depth
    return 1 + max(left_depth, right_depth)  # Add 1 for current node

The work lands after both recursive calls because we need the children's depths before we can compute our own. Postorder, exactly.

Real Example: Validate BST

Validating a BST is where inorder earns its keep. The definition says every left descendant is smaller and every right descendant larger, and if you follow that down recursively, it means an inorder walk must emit strictly increasing values. A single out-of-order pair breaks it.

You could thread min/max bounds down the tree, and that works, but it's more machinery than the problem needs. Run inorder and check that each value beats the previous one. One variable holding the last value seen is the whole trick.

python

def is_valid_bst(root):
    prev = [float('-inf')]       # Track last visited value
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):       # Check left subtree first
            return False
        if node.val <= prev[0]:          # Must be strictly increasing
            return False
        prev[0] = node.val              # Update last visited
        return inorder(node.right)       # Check right subtree
    return inorder(root)

No bounds to pass around. Inorder visits BST nodes in sorted order, so verifying each value tops the last one is enough.

Iterative Traversals

Interviewers sometimes want the iterative version, or you're on a tree deep enough that recursion would blow the call stack. Either way, you swap the implicit call stack for an explicit one.

Preorder converts most cleanly, because its logic already reads like stack operations: pop a node, process it, push its children. The stack is LIFO, so you push the right child before the left, and the left comes back off first to keep root-left-right intact.

python

def preorder_iterative(root):
    if not root: return []
    result, stack = [], [root]       # Start with root on stack
    while stack:
        node = stack.pop()           # Pop and process immediately
        result.append(node.val)
        if node.right: stack.append(node.right)  # Push right first
        if node.left: stack.append(node.left)    # Left pops next
    return result

Inorder is fussier. You have to run all the way down the left spine before you're allowed to process anything, so a single pop-and-print loop won't cut it.

python

def inorder_iterative(root):
    result, stack, cur = [], [], root
    while cur or stack:              # Continue while nodes remain
        while cur:                   # Go left as far as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()            # Process leftmost unvisited
        result.append(cur.val)
        cur = cur.right              # Move to right subtree
    return result

This mirrors what recursion was doing under the hood: dive left, process, then head right. Worth having in your pocket for interviews, though the recursive version is almost always the cleaner thing to write.

Practice

Implement inorder traversal. Write the recursive version first, then rebuild it iteratively with an explicit stack.

Try it yourself

Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Examples

Input: root = [1,null,2,3]

Output: [1,3,2]

Left is null, visit 1, then go right to 2, visit left child 3, then 2

Input: root = []

Output: []

Empty tree

Inorder Traversal

Click "Run" to execute your code

Test Cases

Input: [1,null,2,3]Expected: [1, 3, 2]

Input: []Expected: []

Input: [1]Expected: [1]

Input: [1,2,3,4,5]Expected: [4, 2, 5, 1, 3]

Solution

def solution(nums, target):

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Time: O(log n) | Space: O(1)

View Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Quick Reference

Need sorted order from BST

Inorder

BST inorder = sorted

Copy/clone/serialize tree

Preorder

Need parent before children

Delete tree, free memory

Postorder

Delete children before parent

Calculate height/depth/diameter

Postorder

Need children's results first

Pass value down to children

Preorder

Compute at parent, pass down

Aggregate results up from children

Postorder

Get children, combine at parent

Traversal Order = Problem Structure

The traversal you pick just mirrors how information moves through the problem. Passing something down to children means preorder. Aggregating results up from them means postorder. Wanting BST values in sorted order means inorder. Name the direction the information flows and the traversal picks itself, and the code stops being a decision.

Key Takeaways

Preorder: process before recursing (top-down)
Inorder: process between left and right (BST sorted order)
Postorder: process after recursing (bottom-up)
The traversal name tells you WHEN you process the node
Choose based on information flow: down = preorder, up = postorder

Next: Tree Properties