Maximum Depth of Binary Tree: Height recursion Pattern

Learning Outcome

After this lesson, you should be able to define tree height recursively and return the maximum depth from the root.

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes on the longest path from the root to a leaf.

Brute Force Approach

Store every root-to-leaf path, then return the length of the longest path.

This works but stores unnecessary path lists. The depth can be computed directly.

Optimized Approach

For any node, the maximum depth is 1 + max(depth(left), depth(right)). A null node contributes depth 0.

Exact Pseudocode

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

Reference Code

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
  

Sample Dry Run

Complexity

Edge Cases

• Empty tree returns 0.
• Single-node tree returns 1.
• Skewed tree has height n.

Interview Checklist

• Use 0 for null depth.
• Add 1 for the current node.
• Take the maximum of left and right depth.

FAQs