DSA sheet · Trees · DFS pattern

Maximum Depth & Minimum Depth of a Binary Tree

Two very common warm-up problems, taught together because they look almost the same. The teacher solves maximum depth with BFS (count the levels) and DFS (ask each child for its height). Then she tries the obvious shortcut for minimum depth, changing max to min, and shows on screen that it gives a wrong answer. Fixing that mistake is the most important lesson here: an empty child is not a leaf. Finally she shows BFS makes minimum depth easy: stop at the first leaf you meet.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Maximum depth with BFS (count the levels)
• Part B · Maximum depth with DFS (max of the children + 1)
• Part C · Minimum depth with DFS (the max → min trap, and the fix)
• Part D · Minimum depth with BFS (stop at the first leaf)
• Part E · Revision page

Part 0 · Before starting

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

Words we need

• Leaf: a node with no children at all (both left and right are None).
• Level: a row of the tree. The root is on the first row, its children on the second, and so on.
• Depth of the tree (on LeetCode): the number of nodes on a path that goes from the root down to a leaf. A single node has depth 1, and an empty tree has depth 0.
• Maximum depth: the longest such path. The teacher says this is the same thing as the height of the tree, and also the same as the number of levels.
• Minimum depth: the shortest path from the root down to the nearest leaf.

      3
     / \
    9   20
       /  \
      15   7

    1
     \
      2

In example 2, [1, null, 2] means 1 has no left child and has 2 as its right child. There are 2 levels, so the maximum depth is 2.

Part A · Maximum depth with BFS

LeetCode 104 · Maximum Depth of Binary Tree

1The question in simple words

Given the root, return the number of nodes on the longest path from the root down to a leaf. This is the teacher's own tree for this problem:

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

The longest path is 1 → 3 → 5 → 6, which has 4 nodes. Answer: 4.

2What the constraints tell us

• Number of nodes: 0 to 10⁴.
  • 0 allowed → in BFS we must write the empty check first (return 0).
  • In DFS the base case is needed no matter what the minimum is, because it's the only thing that stops the recursion.
• n up to 10⁴ → an O(n²) idea would be 10⁴ × 10⁴ = 10⁸ steps. The teacher's rule: about 10⁸ is already slow and beyond it you risk TLE. So we want O(n).
• Values: −100 to 100. We'd only care about the range if we were adding or multiplying values (int holds about ±2 × 10⁹; beyond that you need long). Here we never touch the values at all, so it's safe.

3Intuition

Maximum depth = number of levels. BFS level order already walks the tree one level at a time: each round of the outer while loop handles exactly one level. So we just count the rounds.

4Building the logic: edit level order

• Same queue, same size = len(queue), same inner loop that pops the level and pushes children.
• We don't store anything: no sublist, no values. We only need the children to go into the queue.
• Keep a counter depth = 0. After each inner loop (one full level done), do depth += 1.
• When the queue becomes empty, depth is the number of levels.

5Approach steps

1. If the root is None, return 0.
2. Put the root in the queue; depth = 0.
3. While the queue isn't empty: size = len(queue); pop size nodes and push their children.
4. After each level, depth += 1.
5. Return depth.

6Code (Python)

from collections import deque

class Solution:
    def maxDepth(self, root):
        if root is None:                    # 0 nodes allowed
            return 0
        queue = deque([root])
        depth = 0
        while queue:
            size = len(queue)
            for i in range(size):           # pop one whole level
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1                      # one more level finished
        return depth

7Code line by line

8Dry run on the teacher's tree

9Complexity & remember

• Time O(n): every node is pushed and popped once.
• Space O(n) worst case. The teacher's picture: a complete tree with 15 nodes has 8 on the last level, and at one point all 8 sit in the queue together. That's about n/2, which is O(n).

               1
          /         \
        2             3
      /   \         /   \
     4     5       6     7
    / \   / \     / \   / \
   8   9 10  11  12 13 14  15     ← 8 of 15 nodes in the queue at once

Part B · Maximum depth with DFS

1The question, and 2 the constraints

Same question and constraints as Part A. This is recursion, so the base case is mandatory.

3Intuition: ask your children

Stand at the root. From there you can't see how deep the tree goes. But you can ask your left child "how tall is your side?" and your right child "how tall is yours?". In the teacher's tree, the left side (just 2) answers 1, and the right side (3, 4, 5, 6) answers 3.

Your own height is then the taller of the two answers, plus 1 for yourself: max(1, 3) + 1 = 4. Every node does the same thing, asking its own children. That's a recursive function.

height(node) = max(height(left), height(right)) + 1

4Building the logic

The base case: what does an empty spot return?

The teacher's habit: whenever you write a DFS function, start with "what if the node is None?". Since our function returns a height, the answer must be an integer, not a boolean. An empty spot adds no nodes to any path → return 0.

The recursive part

The calls return integers, so store them: left = self.maxDepth(root.left), right = self.maxDepth(root.right).

Max or sum? The teacher asks this explicitly

Look at node 2: left gives 0, right gives 0. What should 2 report to its parent? A node can only hand back one path going down from it. Node 3 has two paths below it (through 4 and through 5), but it can only return one of them, so it returns the longer. Adding them would count two different paths as if they were one. So it's max, not sum, plus 1 for the node itself.

5Approach steps

1. If the node is None, return 0.
2. Get the left height by recursion.
3. Get the right height by recursion.
4. Return max(left, right) + 1.

6Code (Python)

class Solution:
    def maxDepth(self, root):
        if root is None:                    # empty spot adds nothing
            return 0
        left = self.maxDepth(root.left)     # height of the left side
        right = self.maxDepth(root.right)   # height of the right side
        return max(left, right) + 1         # taller side + me

7Code line by line

The main function is the DFS itself here. With a separate helper, the main function would just return dfs(root).

8Dry run with the call stack

1. f(1) → go left: f(2) → go left: f(None) → 0, leaves the stack. f(2) right: f(None) → 0.
2. f(2) has left 0, right 0 → max(0, 0) + 1 = 1. 2 leaves the stack; f(1) now has left = 1.
3. f(1) goes right: f(3) → left: f(4) → its children give 0 and 0 → returns 1. f(3) has left = 1.
4. f(3) goes right: f(5) → left: f(6) → children 0, 0 → returns 1. f(5) has left = 1.
5. f(5) right: f(None) → 0. f(5) returns max(1, 0) + 1 = 2 to f(3), as its right value. (In the video she first says "six's right", then corrects herself: it's 3's right.)
6. f(3) has left 1, right 2 → max + 1 = 3 → f(1)'s right = 3.
7. f(1): max(1, 3) + 1 = 4. The stack is empty; 4 goes back to the caller ✓

9Complexity & remember

• Time O(n): every node is visited once.
• Space O(height), for the call stack. In the dry run the stack was at most 1, 3, 5, 6: four calls, one per level. For a balanced tree the number of levels is about log n. For a skewed tree (all nodes leaning to one side, like a chain) the number of levels is about n, so the worst case is O(n).

Part C · Minimum depth with DFS

LeetCode 111 · Minimum Depth of Binary Tree

1The question in simple words

Return the number of nodes on the shortest path from the root down to a leaf. Remember, a leaf is a node with no children.

      3
     / \
    9   20       9 is a leaf: 3 → 9 = 2 nodes
       /  \
      15   7

  2
   \
    3
     \
      4
       \
        5
         \
          6       the only leaf is 6: 5 nodes

2What the constraints tell us

• 0 nodes allowed → the empty tree must return 0. In DFS the base case does that.
• Up to 10⁵ nodes on LeetCode → O(n) needed.

3Intuition: first try the obvious copy

Minimum depth sounds like max depth with max swapped for min. The teacher does exactly that: copies the max depth code, renames it, changes max to min, and runs it.

class Solution:
    def minDepth(self, root):
        if root is None:
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        return min(left, right) + 1         # WRONG when one child is missing

Example 1 passes (2). Example 2 fails: it returns 1, but the answer is 5.

4Building the logic: why it fails, and the fix

What goes wrong on example 2

Stand at the root 2. Its left child is None, so the left call returns 0. The right side (3, 4, 5, 6) returns 4. The code returns min(0, 4) + 1 = 1. It's acting as if the path "2 → nothing" ended at a leaf after 1 node.

But a missing child is not a leaf. A leaf is a real node with no children. Root 2 has a child, so 2 is not a leaf, and no path can stop at 2. The 0 from the empty side is not a path at all, so it must not win the min.

The fix: only compare when both children exist

• No left child → every path must go right → return minDepth(right) + 1.
• No right child → every path must go left → return minDepth(left) + 1.
• Both children exist → now both sides are real paths → return min(left, right) + 1.

5Approach steps

1. If the node is None, return 0.
2. If the left child is None, return minDepth(right) + 1.
3. If the right child is None, return minDepth(left) + 1.
4. Otherwise return min(minDepth(left), minDepth(right)) + 1.

6Code (Python)

class Solution:
    def minDepth(self, root):
        if root is None:
            return 0
        if root.left is None:               # only the right side has paths
            return self.minDepth(root.right) + 1
        if root.right is None:              # only the left side has paths
            return self.minDepth(root.left) + 1
        left = self.minDepth(root.left)     # both exist: compare them
        right = self.minDepth(root.right)
        return min(left, right) + 1

7Code line by line

8Dry run on example 2

1. f(2): left is None → return f(3) + 1. (The wrong version would have used the 0 here.)
2. f(3): left is None → return f(4) + 1.
3. f(4): left is None → f(5) + 1. f(5): left is None → f(6) + 1.
4. f(6): a leaf → left is None → f(None) + 1 = 0 + 1 = 1.
5. Coming back up: f(5) = 2, f(4) = 3, f(3) = 4, f(2) = 5 ✓

On example 1: f(3) has both children → min(f(9), f(20)) + 1. f(9) is a leaf → 1. f(20) → both children are leaves → min(1, 1) + 1 = 2. So f(3) = min(1, 2) + 1 = 2 ✓

9Complexity & remember

• Time O(n): each node is visited once.
• Space O(height) for the call stack: about log n if balanced, O(n) if skewed (like example 2).

Part D · Minimum depth with BFS

1The question, and 2 the constraints

Same as Part C. 0 nodes allowed, so BFS needs the empty check: return 0.

3Intuition: the first leaf you meet is the answer

The teacher says this is even easier with BFS. BFS visits the tree level by level, from the top. So the first leaf it pops is on the shallowest level that has any leaf. Return that level's number right there, and don't look any further.

Her example: take example 2's chain and add one extra leaf, 5, as the left child of the root:

      2             level 1
     / \
    5   3           level 2   ← 5 is a leaf → answer 2
         \
          4
           \
            5
             \
              6     (the chain's leaf, level 5)

Pop 2: not a leaf, push 5 and 3. Next level: pop 5: leaf → return 2. We never even look at 4, the second 5, or 6. Without the leaf check, BFS would keep going all the way down to 6 and count 5 levels, which is the maximum depth.

For the plain chain in example 2, the only leaf is 6 at the bottom, so here the minimum and maximum depth are the same: 5.

4Building the logic: edit max depth BFS

• Copy the max depth BFS code.
• Start depth = 1, not 0, because the root we put in the queue is already on level 1.
• Right after popping a node, check: node.left is None and node.right is None? If so, it's a leaf → return depth.
• Otherwise push its children as usual, and after each level depth += 1.
• The final return after the loop is never reached for a non-empty tree (every tree has at least one leaf). Java needs a return there to compile; in Python it's just a safety line.

5Approach steps

1. If the root is None, return 0.
2. Queue = [root], depth = 1.
3. While the queue isn't empty: pop the whole level. For each node, if it's a leaf, return depth; else push its children.
4. After each level, depth += 1.

6Code (Python)

from collections import deque

class Solution:
    def minDepth(self, root):
        if root is None:
            return 0
        queue = deque([root])
        depth = 1                           # the root is level 1
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if node.left is None and node.right is None:
                    return depth            # first leaf = shallowest leaf
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth                        # never reached for a real tree

7Code line by line

8Dry run

Her tree with the extra leaf 5

LeetCode example 1

Example 2 (the chain)

9Complexity & remember

• Time O(n) in the worst case (when the first leaf is deep). Often much less, because it stops early.
• Space O(n) worst case for the queue (the widest level).

Part E · Revision page

t = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5, TreeNode(6))))
ex1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
chain = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))

s = Solution()
print(s.maxDepth(t))       # 4
print(s.maxDepth(ex1))     # 3
print(s.minDepth(ex1))     # 2
print(s.minDepth(chain))   # 5
print(s.minDepth(None))    # 0

Based on this video: Maximum & Minimum Depth of Binary Tree | DFS & BFS