Exercise 1: Maximum Depth of a Binary Tree 📏

Your Task

Write a function max_depth(root) that returns the maximum depth (height) of a binary tree.

The depth is the number of nodes along the longest path from the root to a leaf node.

---

Examples

#     3
#    / \
#   9  20
#     /  \
#    15   7

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(max_depth(root))  # 3

#   1
#    \
#     2

root = TreeNode(1)
root.right = TreeNode(2)

print(max_depth(root))  # 2

print(max_depth(None))  # 0

---

Expected Complexity

	Complexity
Time	O(n) — visit every node once
Space	O(h) — recursion stack, h = height

---

Approach

1. Base case: if root is None, return 0
2. Recursively find the depth of the left subtree
3. Recursively find the depth of the right subtree
4. Return 1 + max(left_depth, right_depth)

---

Hints