Tree Traversal Patterns: BFS, DFS, Inorder, and Beyond

Trees are everywhere in coding interviews. From binary search trees to n-ary trees, almost every interview round includes at least one tree problem. The good news? Every tree problem boils down to choosing the right traversal. Master the four core traversals and you can solve the vast majority of tree questions on LeetCode and in FAANG interviews.

This guide covers Inorder, Preorder, Postorder, and Level Order traversals with both recursive and iterative Python implementations, walks through four classic LeetCode problems, and gives you a decision framework so you always know which traversal to reach for.

The 4 Core Tree Traversals

Every traversal visits every node exactly once. The difference is when you process the current node relative to its children.

Recursive vs Iterative Implementations

Recursive solutions are shorter and easier to write, but iterative versions avoid stack overflow on deep trees and give you finer control over traversal. Interviewers sometimes ask for both.

Inorder Traversal

# Recursive Inorder
def inorder_recursive(root):
    if not root:
        return []
    return (inorder_recursive(root.left)
            + [root.val]
            + inorder_recursive(root.right))

# Iterative Inorder (using explicit stack)
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

Preorder Traversal

# Recursive Preorder
def preorder_recursive(root):
    if not root:
        return []
    return ([root.val]
            + preorder_recursive(root.left)
            + preorder_recursive(root.right))

# Iterative Preorder
def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Postorder Traversal

# Recursive Postorder
def postorder_recursive(root):
    if not root:
        return []
    return (postorder_recursive(root.left)
            + postorder_recursive(root.right)
            + [root.val])

# Iterative Postorder (two-stack method)
def postorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]  # Reverse to get postorder

Level Order Traversal (BFS)

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            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

When to Use Which Traversal

Choosing the right traversal is the single most important decision in any tree problem. Here is the framework:

BFS vs DFS on Trees

BFS and DFS are not competing strategies — they serve different purposes. On trees specifically, here is when each shines:

For a deeper comparison beyond trees, including graph traversal scenarios, check out our BFS vs DFS interactive comparison.

Step-by-Step LeetCode Examples

Let's put each traversal to work on a classic problem.

1. Binary Tree Level Order Traversal (LC 102) — BFS

Problem: Given the root of a binary tree, return the level order traversal as a list of lists. Each inner list contains the values at that depth.

Why BFS: We need to group nodes by their depth. BFS with a queue naturally processes one complete level before moving to the next.

from collections import deque

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

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            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

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

The key insight: snapshot the queue length at the start of each level. That tells you exactly how many nodes belong to the current depth.

2. Maximum Depth of Binary Tree (LC 104) — DFS

Problem: Given the root of a binary tree, return its maximum depth (number of nodes along the longest root-to-leaf path).

Why DFS: Depth is a bottom-up calculation — you need the depth of both subtrees before you can compute the depth of the current node.

def maxDepth(root):
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

# Time: O(n)  |  Space: O(h) where h = height

This is the simplest postorder pattern: compute something for each subtree, then combine the results at the current node. The same skeleton solves dozens of tree problems.

3. Validate Binary Search Tree (LC 98) — Inorder

Problem: Determine if a binary tree is a valid BST (every node's left subtree contains only values less than the node, and the right subtree only values greater).

Why Inorder: A valid BST's inorder traversal produces a strictly increasing sequence. Just check that each value is greater than the previous.

def isValidBST(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)

# Time: O(n)  |  Space: O(h)

We use a mutable container (prev[0]) to track the previously visited value across recursive calls. The moment any value is not strictly greater, we short-circuit and return False.

4. Diameter of Binary Tree (LC 543) — Postorder

Problem: The diameter is the length of the longest path between any two nodes (measured in edges). The path does not need to pass through the root.

Why Postorder: At each node, the longest path through that node is left_height + right_height. We need both subtree heights before we can compute this, which is exactly what postorder provides.

def diameterOfBinaryTree(root):
    diameter = [0]

    def height(node):
        if not node:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        # Update diameter: path through this node
        diameter[0] = max(diameter[0], left_h + right_h)
        return max(left_h, right_h) + 1

    height(root)
    return diameter[0]

# Time: O(n)  |  Space: O(h)

Notice the dual purpose of the recursion: it returns the height (used by the parent) while simultaneously tracking the global diameter. This "return one thing, update another" pattern appears in many postorder problems.

Advanced Tree Patterns

Morris Traversal — O(1) Space Inorder

Morris traversal achieves O(1) space by temporarily threading the tree: it links each node's inorder predecessor's right child back to the node, allowing traversal without a stack. After visiting a node, it restores the original tree structure.

def morris_inorder(root):
    result = []
    current = root

    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if not predecessor.right:
                # Create thread
                predecessor.right = current
                current = current.left
            else:
                # Remove thread, visit node
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result

# Time: O(n)  |  Space: O(1) — no stack needed

Morris traversal is rarely required in interviews, but mentioning it demonstrates deep understanding and can score bonus points. The key trade-off: it temporarily modifies the tree.

Iterative DFS with Explicit Stack

For very deep trees (or languages without tail-call optimization), an explicit stack avoids stack overflow. The iterative inorder we showed earlier is the most common variant. Iterative postorder is trickier — the cleanest approach is to run a modified preorder (Root → Right → Left) and reverse the result.

Another advanced technique is using a stack with state flags — push tuples of (node, visited) so you know whether to expand children or process the node:

def postorder_with_flag(root):
    if not root:
        return []
    result = []
    stack = [(root, False)]

    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)
        else:
            # Postorder: push root (marked), then right, then left
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))

    return result

This unified approach works for all three DFS orders — just change the push order on the stack.

Practice Problems by Traversal Type

Solidify your understanding with these 10 problems, organized by the traversal they require.

Inorder (BST Problems)

Preorder (Serialize / Construct)

Postorder (Bottom-Up)

Level Order (BFS)

Explore These Patterns on AlgoArk

Dive deeper with our interactive pattern walkthroughs and animated visualizations:

• BFS (Level-Order) Pattern — Interactive Walkthrough
• DFS (Pre/In/Post-Order) Pattern — Interactive Walkthrough
• BFS vs DFS — Side-by-Side Comparison

Related reads:

• BFS vs DFS: When to Use Which
• Graph Patterns Guide
• Top 10 LeetCode Patterns Every FAANG Candidate Must Know