Maximum Depth of Binary Tree

Learning goal: Recognize maximum depth as the length of the longest root-to-leaf path.

Core idea Depth counts nodes, not edges. An empty tree has depth 0; a tree containing only its root has depth 1. For a larger tree, the answer is determined by whichever child subtree reaches farther from the current node.

Algorithm plan

• Start at the root.
• Explore both the left and right subtrees.
• Keep the larger subtree depth.
• Add 1 for the current node.

Micro-example For 3 → 20 → 15, the path contains three nodes, so its depth is 3. For an empty child such as the left child of 9, the depth is 0.

Pitfalls

• Counting edges instead of nodes produces an answer that is one too small.
• Forgetting the empty-tree case makes root = null fail.
• Only following one child misses a deeper path on the other side.

Recap

• Depth is a longest-path measurement.
• A leaf has depth 1.
• The empty tree has depth 0.

Learning goal: Derive the recurrence that turns a tree problem into smaller subtree problems.

Core idea Once we know the depth of the left and right subtrees, the current node contributes exactly one additional level. Therefore, the deeper subtree determines the answer below this node, and the current node is added afterward.

Recurrence

depth(node) = 0 when node is null.

depth(node) = 1 + max(depth(node.left), depth(node.right)) otherwise.

Algorithm plan

maxDepth(node):
    if node is null:
        return 0
    leftDepth = maxDepth(node.left)
    rightDepth = maxDepth(node.right)
    return 1 + max(leftDepth, rightDepth)

Micro-example For node 20, the subtree rooted at 15 has depth 1, and the subtree rooted at 7 has depth 1. Thus depth(20) = 1 + max(1, 1) = 2.

Pitfalls

• Applying 1 + max(...) to null would make empty children incorrectly contribute a level.
• Returning max(left, right) without the 1 omits the current node.
• The recursive calls must explore both children.

Recap

• Solve two smaller instances, then combine them.
• null contributes 0.
• The current node contributes 1.

Learning goal: Compare recursive DFS with level-order BFS and understand why both are linear-time traversals.

Core idea Recursive DFS computes a numerical answer while returning from each subtree. BFS instead processes the tree one level at a time; after finishing one queue layer, it increments a level counter. Both approaches must inspect every reachable node because any node could extend the deepest path.

Algorithm plan

• DFS: Define the recurrence, recurse on both children, and combine returned depths.
• BFS: Put the root in a queue, process all nodes currently in the queue, enqueue their children, and increment the level count after each layer.
• Choose DFS when the recurrence is the clearest expression of the problem.
• Choose BFS when level boundaries or minimum distance are central to the task.

Here, n is the number of nodes, h is the tree height, and w is the maximum width. For this lesson, the recursive DFS is the main implementation and h is the target auxiliary-space measure.

Micro-example DFS visits 3, explores 9, then explores 20 and its children before combining results. BFS would process [3], then [9,20], then [15,7], producing three levels.

Pitfalls

• Calling BFS space O(h) in every tree shape is inaccurate; its queue is O(w).
• A recursive implementation uses stack space even though it does not allocate a separate queue.
• Traversal order changes, but the final depth does not.

Recap

• DFS follows the recurrence directly.
• BFS counts completed levels.
• Both visit each node once.

Learning goal: Trace how subtree answers return upward to produce the final depth.

Core idea Use the example root = [3,9,20,null,null,15,7]. DFS first reaches the leaves, where each leaf returns 1. Those values then flow upward: node 20 receives two child depths of 1 and returns 2, while node 3 receives 1 and 2 and returns 3.

Worked calculation

def maxDepth(node):
    if node is None:
        return 0
    return 1 + max(maxDepth(node.left), maxDepth(node.right))

For node 9, both children are null, so depth(9) = 1 + max(0, 0) = 1. For node 20, both children are leaves, so depth(20) = 1 + max(1, 1) = 2. Finally, depth(3) = 1 + max(1, 2) = 3.

Pitfalls

• Do not combine node 20 before both child calls return.
• The final answer is the value returned by the root, not the number of recursive calls.
• A null child is a valid completed subproblem.

Recap

• Leaves return 1.
• Results are combined during the return phase.
• The root returns the complete tree depth.

Learning goal: Guard against the base-case and counting mistakes that most often break this solution.

Core idea The recurrence is short, but its base case defines the meaning of every returned value. A null pointer represents no node and therefore contributes 0; a leaf has two null children, so it returns 1. This convention makes the recurrence work uniformly for every non-null node.

Edge-case checklist

• Empty tree: maxDepth(null) = 0.
• Single node: both children are null, so the answer is 1.
• One-sided chain: every node adds one, producing the chain length.
• Balanced tree: compare both branches at every internal node.

Micro-example

For [1,null,2], node 2 returns 1. Then node 1 returns 1 + max(0, 1) = 2, not 1.

Pitfalls

• Returning 0 for a leaf confuses a node with an empty child.
• Returning 1 for null makes every path too deep.
• Testing only balanced trees can hide errors on skewed trees.
• A very deep skewed tree can approach recursion depth limits in some languages.

Recap

• Null means no level: 0.
• A leaf is one level: 1.
• Test empty, single-node, and one-sided trees.

Learning goal: Justify the performance of the recursive traversal and summarize the reusable pattern.

Core idea Each node is entered once and its two child references are examined once. The work therefore grows linearly with the number of nodes. The recursion stack stores the active path from the root to the current node, so its auxiliary space is proportional to the tree height h.

Complexity

For a balanced tree, h is about log n. For a completely skewed tree, h can be n. BFS also takes O(n) time, but its queue uses O(w) space, where w is the maximum width.

Micro-example The example has five nodes, and DFS visits all five exactly once. Its deepest active path has three nodes, so the recursion uses O(h) space with h = 3.

Pitfalls

• Do not claim constant space for recursive DFS.
• Do not confuse height h with the number of nodes n.
• BFS and DFS share time complexity, but not always auxiliary-space complexity.

Recap

• Recurrence: 1 + max(left, right).
• Base case: null contributes 0.
• Performance: O(n) time and O(h) recursive space.