Binary Tree Traversal: Master DFS, BFS & Recursion for Coding Interviews

The Recursive Insight That Changed Everything

Tree problems used to terrify me. The recursive solutions felt like magic—how did people just "know" to return 1 + max(left, right) for tree height? How did they elegantly handle null nodes without cluttering their code with null checks?

Then I realized something profound: most tree problems are just variations of 6 core patterns. Once you recognize the pattern, the solution practically writes itself. You're not inventing algorithms from scratch—you're applying templates.

In this guide, I'll share the systematic approach that transformed trees from my interview weakness to my strength. You'll learn to recognize patterns instantly and code solutions confidently.

Why Tree Problems Feel Different

Trees are fundamentally recursive data structures—a tree is either empty, or a node with two subtrees (which are also trees). This recursive nature means:

1. Most solutions are naturally recursive2. Base cases are crucial (null nodes)3. You combine information from subtrees

The key insight: solve the problem for subtrees, then combine results at the root.

The Six Core Tree Patterns

Pattern 1: Tree Traversals (The Foundation)

Before anything else, you must master the four traversal orders. They're the building blocks for every tree algorithm.

Inorder (Left → Root → Right):

def inorder(root):
    """
    Inorder traversal: left subtree, root, right subtree.
    For BST, gives sorted order.
    """
    if not root:
        return []

    result = []
    result.extend(inorder(root.left))    # Left
    result.append(root.val)               # Root
    result.extend(inorder(root.right))   # Right

    return result

Preorder (Root → Left → Right):

def preorder(root):
    """
    Preorder traversal: root, left subtree, right subtree.
    Useful for serialization, copying trees.
    """
    if not root:
        return []

    result = []
    result.append(root.val)               # Root
    result.extend(preorder(root.left))   # Left
    result.extend(preorder(root.right))  # Right

    return result

Postorder (Left → Right → Root):

def postorder(root):
    """
    Postorder traversal: left subtree, right subtree, root.
    Useful for deletion, calculating properties.
    """
    if not root:
        return []

    result = []
    result.extend(postorder(root.left))   # Left
    result.extend(postorder(root.right))  # Right
    result.append(root.val)                # Root

    return result

Level-order (BFS):

from collections import deque

def level_order(root):
    """
    Level-order traversal: level by level, left to right.
    Uses queue for BFS.
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

When to use which:

• Inorder: BST problems (gives sorted order), range queries
• Preorder: Serialization, tree copying, prefix expressions
• Postorder: Tree deletion, calculating properties from children
• Level-order: Level-based problems, shortest path, BFS

Pattern 2: Recursive Information Passing (Bottom-Up)

This is the most common tree pattern. You recursively solve for left and right subtrees, then combine results.

Template:

def tree_property(root):
    """
    Bottom-up pattern: get info from children, combine at root.
    """
    # Base case: null node
    if not root:
        return base_value

    # Recurse on children
    left_result = tree_property(root.left)
    right_result = tree_property(root.right)

    # Combine results
    return combine(left_result, right_result, root.val)

Example: Tree Height

def max_depth(root):
    """
    Find height of tree using bottom-up recursion.
    Height = 1 + max(left_height, right_height).
    """
    if not root:
        return 0

    left_height = max_depth(root.left)
    right_height = max_depth(root.right)

    return 1 + max(left_height, right_height)

Example: Tree Diameter

LeetCode #543 - Diameter of Binary Tree

def diameter(root):
    """
    Find diameter: longest path between any two nodes.
    At each node, consider path through that node.
    """
    max_diameter = [0]  # Use list to modify in nested function

    def height(node):
        """Return height while updating diameter."""
        if not node:
            return 0

        left_height = height(node.left)
        right_height = height(node.right)

        # Diameter through this node
        path_through_node = left_height + right_height
        max_diameter[0] = max(max_diameter[0], path_through_node)

        # Return height for parent
        return 1 + max(left_height, right_height)

    height(root)
    return max_diameter[0]

Key insight: We calculate two things at each node:

1. Height (returned to parent)
2. Diameter through this node (stored globally)

This "calculate multiple things during recursion" pattern is very common.

Pattern 3: Top-Down Information Passing

Sometimes you need to pass information from parent to children—constraints, accumulated values, paths.

Template:

def top_down_pattern(root, parent_info):
    """
    Top-down pattern: pass info from parent to children.
    """
    if not root:
        return

    # Process current node with parent info
    process(root, parent_info)

    # Pass updated info to children
    top_down_pattern(root.left, update(parent_info))
    top_down_pattern(root.right, update(parent_info))

Example: Path Sum

LeetCode #112 - Path Sum

def has_path_sum(root, target_sum):
    """
    Check if root-to-leaf path sums to target.
    Pass remaining sum down the tree.
    """
    if not root:
        return False

    # At leaf node, check if we've reached target
    if not root.left and not root.right:
        return root.val == target_sum

    # Pass reduced target to children
    remaining = target_sum - root.val

    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

Key insight: We subtract current node's value and pass the remaining sum down. At leaves, we check if we've hit exactly zero.

Example: All Root-to-Leaf Paths

def all_paths(root):
    """
    Find all root-to-leaf paths.
    Build path as we go down.
    """
    result = []

    def dfs(node, current_path):
        if not node:
            return

        # Add current node to path
        current_path.append(node.val)

        # At leaf: save path
        if not node.left and not node.right:
            result.append(current_path[:])  # Copy path
        else:
            # Recurse on children
            dfs(node.left, current_path)
            dfs(node.right, current_path)

        # Backtrack: remove current node
        current_path.pop()

    dfs(root, [])
    return result

Key insight: We build the path as we descend, save it at leaves, and backtrack (remove node) when returning. This is similar to backtracking pattern.

Pattern 4: Lowest Common Ancestor (LCA)

This is a specific but important pattern that comes up frequently.

LeetCode #236 - Lowest Common Ancestor of Binary Tree

def lowest_common_ancestor(root, p, q):
    """
    Find LCA of two nodes.
    LCA is deepest node that has both p and q in its subtrees.
    """
    # Base cases
    if not root or root == p or root == q:
        return root

    # Search in both subtrees
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    # Both found in different subtrees → current is LCA
    if left and right:
        return root

    # Return whichever side found something
    return left if left else right

Why this works:

1. If current node is p or q, return it
2. Search both subtrees
3. If both subtrees return non-null, current node is LCA
4. If only one returns non-null, return that (LCA is in that subtree)

Brilliant insight: This works because the first node where both p and q appear in different subtrees is the LCA by definition.

Pattern 5: Binary Search Tree (BST) Properties

BSTs have special properties: left < root < right. This enables efficient operations.

Validate BST:

def is_valid_bst(root):
    """
    Validate BST: all left nodes < root < all right nodes.
    Pass min/max bounds down.
    """
    def validate(node, min_val, max_val):
        if not node:
            return True

        # Check if current node violates BST property
        if node.val <= min_val or node.val >= max_val:
            return False

        # Recurse with updated bounds
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))

Key insight: We pass down valid range (min, max) for each subtree. Left subtree must be in (min, root.val), right in (root.val, max).

Find Kth Smallest in BST:

LeetCode #230 - Kth Smallest Element in BST

def kth_smallest(root, k):
    """
    Find kth smallest element in BST.
    Inorder traversal gives sorted order!
    """
    result = []

    def inorder(node):
        if not node or len(result) >= k:
            return

        inorder(node.left)

        if len(result) < k:
            result.append(node.val)

        inorder(node.right)

    inorder(root)
    return result[-1] if result else None

Key insight: Inorder traversal of BST gives sorted order. Stop after collecting k elements.

Pattern 6: Serialization and Construction

Converting trees to/from strings or arrays is a common pattern.

Serialize and Deserialize:

LeetCode #297 - Serialize and Deserialize Binary Tree

class Codec:
    """
    Serialize tree to string, deserialize back to tree.
    Use preorder traversal with None markers.
    """

    def serialize(self, root):
        """Encode tree to string."""
        result = []

        def preorder(node):
            if not node:
                result.append('null')
                return

            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return ','.join(result)

    def deserialize(self, data):
        """Decode string to tree."""
        values = iter(data.split(','))

        def build():
            val = next(values)
            if val == 'null':
                return None

            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()

Key insight: Preorder traversal naturally captures tree structure. During deserialization, we consume values in the same order we produced them.

Construct Tree from Traversals:

LeetCode #105 - Construct Binary Tree from Preorder and Inorder

def build_tree(preorder, inorder):
    """
    Build tree from preorder and inorder traversals.
    Preorder gives root, inorder gives left/right split.
    """
    if not preorder or not inorder:
        return None

    # First element in preorder is root
    root = TreeNode(preorder[0])

    # Find root in inorder to split left/right
    mid = inorder.index(preorder[0])

    # Build left and right subtrees
    root.left = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:], inorder[mid+1:])

    return root

Key insight:

• First element of preorder = root
• Find root in inorder → everything left is left subtree, right is right subtree
• Recurse on subarrays

DFS vs BFS: When to Use Which

Use DFS (recursion or stack) when:

• You need to explore all paths
• You need to track path information
• Problem involves going deep before wide
• Examples: path sum, tree diameter, serialization

Use BFS (queue) when:

• You need level-by-level processing
• You need shortest path (unweighted)
• You need to find closest/shallowest node
• Examples: level order, minimum depth, right side view

Common Tree Pitfalls

Mistake 1: Not Handling Null Nodes

# WRONG: Will crash on null
if root.left.val == target:

# RIGHT: Check for null first
if root.left and root.left.val == target:

Mistake 2: Modifying Tree While Traversing

# WRONG: Lost reference
node.left = None
process(node.left)  # node.left is now None!

# RIGHT: Save reference
left_child = node.left
node.left = None
process(left_child)

Mistake 3: Forgetting Leaf Node Edge Case

# Always check if node is leaf
if not node.left and not node.right:
    # This is a leaf, handle specially

Mistake 4: Confusing BST with General Binary Tree

BST property: left < root < right for ALL descendants, not just children.

# WRONG: Only checks immediate children
def is_bst(root):
    if root.left and root.left.val >= root.val:
        return False
    # This misses: right child of left subtree > root

# RIGHT: Pass min/max bounds

The Tree Problem Decision Tree

When you see a tree problem:

1. Does it involve traversal order?

• Sorted order needed? → Inorder (for BST)
• Need to process levels? → Level-order (BFS)
• Need to serialize? → Preorder or Postorder

2. Does it ask for a property (height, diameter, balanced)?

• Likely bottom-up recursion
• Get info from children, combine at root

3. Does it involve paths or sums?

• Likely top-down recursion
• Pass accumulated info from parent to children

4. Is it a BST problem?

• Use BST property: left < root < right
• Often simpler than general tree solutions

5. Does it ask for construction or serialization?

• Use preorder/inorder or level-order
• Pattern 6 (serialization)

6. Does it involve two nodes (LCA, distance)?

• Likely LCA pattern
• Find common ancestor first

My Practice Strategy

Here's how I mastered tree problems:

Week 1: Master Traversals

• Implement all 4 traversals (recursive and iterative) 10 times
• Practice without looking
• Draw trees and trace execution

Week 2: Bottom-Up Recursion

• Height, diameter, balanced tree, symmetric tree
• Focus on combining results from subtrees
• 15-20 problems

Week 3: Top-Down and Paths

• Path sum variations, all paths, serialize
• Practice backtracking for path problems
• 15-20 problems

Week 4: BST and Advanced

• Validate BST, kth element, LCA
• Construction problems
• 20-30 mixed problems

Real Interview Success

I was asked: "Find the maximum path sum in a binary tree (path can start/end anywhere)."

My thought process:

1. "Property of tree + optimization" → Bottom-up recursion
2. At each node, calculate: max path through this node
3. Track global maximum
4. Return to parent: max path ending at this node

Coded in 15 minutes:

def max_path_sum(root):
    max_sum = [float('-inf')]

    def max_gain(node):
        if not node:
            return 0

        # Get max gain from children (ignore negative)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Path through this node
        path_sum = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], path_sum)

        # Return max path ending at this node
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]

The interviewer was impressed by the systematic approach.

Conclusion: Your Tree Mastery Roadmap

Trees aren't as complex as they seem. Here's what matters:

1. Master the four traversals - Everything builds on these
2. Think recursively - Trees are recursive structures
3. Always handle null nodes - First line of every function
4. Identify the pattern - Bottom-up vs top-down vs LCA
5. For BST, use the property - It simplifies many problems

Start with traversals. Make them automatic. Then move to simple recursion (height, diameter). Finally, tackle complex problems (LCA, serialization, path sums).

Within 4 weeks of focused practice, tree problems will feel natural and intuitive.

Remember: every tree expert once struggled with recursion. The difference is they practiced until the patterns became second nature.

Happy coding, and may your trees always be balanced!

If you found this guide helpful, share it with others learning data structures. Trees are fundamental—mastering them opens doors to graphs, heaps, and advanced algorithms. If this guide helped you master tree traversals or understand tree patterns for interviews, I'd love to hear about it! Connect with me on Twitter or LinkedIn.

Support My Work

If this guide helped you finally understand tree traversals, gave you confidence with recursive thinking, or helped you ace tree interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.

☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!

Cover image by ian dooley on Unsplash