Trees and DFS/BFS: Traversal Patterns with Real LC Walkthroughs

Projectsmedium30 min
Ask Cairnly about this lesson
On this page

What you will learn

  • Implement inorder, preorder, postorder DFS both recursively and iteratively
  • Implement level-order BFS using a queue
  • Solve classic tree problems: max depth, invert tree, lowest common ancestor, validate BST
  • Recognize which traversal order fits which problem type

Why this matters

Tree problems make up roughly 20% of coding interview questions. Unlike arrays where you can often wing it, tree problems require you to know your traversal patterns cold. The good news: once you internalize DFS and BFS templates, most tree problems become variations of the same two ideas.

Binary tree node

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

DFS traversals

The three DFS orders differ only in when you process the current node relative to its children.

python
def inorder(root):
    """Left -> Node -> Right. Gives sorted order for BSTs."""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)
 
def preorder(root):
    """Node -> Left -> Right. Useful for serialization / copying a tree."""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)
 
def postorder(root):
    """Left -> Right -> Node. Useful when you need children's results first."""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

BFS (level-order traversal)

Process nodes level by level using a queue.

python
from collections import deque
 
def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # process one level at a time
            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) for all traversals. Space: O(n) worst case (skewed tree for DFS, full level for BFS).

Walkthrough: Maximum Depth of Binary Tree (LC 104)

python
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

This is postorder DFS: compute children's depths first, then combine. One line of logic.

Walkthrough: Invert Binary Tree (LC 226)

python
def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

Walkthrough: Lowest Common Ancestor (LC 236)

python
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root      # p and q are in different subtrees
    return left or right  # both are in the same subtree

Key insight: If both left and right recursive calls return non-None, the current node is the LCA.

Walkthrough: Validate BST (LC 98)

python
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return (is_valid_bst(root.left, lo, root.val) and
            is_valid_bst(root.right, root.val, hi))

Pass down valid ranges. Each node must be within (lo, hi). Left children tighten the upper bound; right children tighten the lower bound.

DFS vs. BFS: when to use which

Problem typePreferred traversal
Max/min depth, path sum, validate BSTDFS (recursion is natural)
Level-order output, shortest path in unweighted treeBFS
Serialize/deserializeEither (preorder DFS or BFS)
Lowest common ancestorDFS (postorder)

Try it yourself

  1. LC 104 - Maximum Depth: Implement using both DFS and BFS. Compare the code length.
  2. LC 102 - Binary Tree Level Order Traversal: Return the values level by level as a list of lists.
  3. LC 236 - Lowest Common Ancestor: Trace through a sample tree by hand to see why the algorithm works.
  4. LC 98 - Validate Binary Search Tree: Try the range-passing approach and the inorder-traversal approach. Which feels more natural to you?
python
# Complete working solutions for self-study
 
from collections import deque
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Build a sample tree:      3
#                          /   \
#                         9     20
#                              /  \
#                             15   7
 
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
 
# DFS - max depth
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))
 
print("Max depth:", max_depth(root))  # 3
 
# BFS - level order
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
 
print("Level order:", level_order(root))  # [[3], [9, 20], [15, 7]]
 
# Validate BST
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)
 
print("Is valid BST:", is_valid_bst(root))  # False (3 < 9, so left child violates)

Checklist

  • I can implement DFS (inorder, preorder, postorder) from memory
  • I can implement BFS with a queue and process nodes level by level
  • I solved Maximum Depth using DFS
  • I solved Level Order Traversal using BFS
  • I understand the range-passing technique for validating a BST
  • I can explain the Lowest Common Ancestor algorithm and why it works

Common mistakes

  • Forgetting the base case: Always handle if not root: return ... first. Missing this causes AttributeError: 'NoneType' has no attribute 'val'.
  • Validating BST by only checking immediate children: Checking node.left.val < node.val is not enough. A node deep in the left subtree could still violate the BST property. You must pass down the valid range.
  • Modifying the tree unintentionally: In problems like LCA, make sure you're returning values up the call stack, not mutating nodes.
  • Using DFS when BFS is simpler: If the problem asks for level-by-level output or shortest path, BFS is more natural and avoids the need to track depth manually.

Quick quiz

Q: In a BST with n nodes, what does an inorder traversal produce?

How to explain it in an interview

"For tree problems, I first decide between DFS and BFS. If I need level-by-level processing or shortest path, I use BFS with a queue. For most other problems like depth, path sum, or validation, I use recursive DFS. For LCA, I use postorder DFS: recurse into both subtrees, and if both return non-null, the current node is the ancestor. For BST validation, I pass a valid range (lo, hi) down the recursion and check each node falls within it."