Maximum Depth of Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the number of levels (depth) of a binary tree.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What is the depth of an empty tree?
- Hint 2The depth of a node's tree is based on its left and right depths.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
An office building's org chart: how many levels does the company have? The CEO does not count the floors himself. He asks his two direct reports: "how many levels are under you?" Each asks their own reports the same thing. The CEO takes the bigger answer and adds one for himself.
- The obvious way
No faster way exists; every node must be seen. The cleanest way is recursion.
- The key insight
depth(node) = 0 for nothing, otherwise 1 + max(depth(left), depth(right)). Each node is visited once.
- The algorithm
- Empty spot? Depth 0.
- Ask the left child for its depth and the right child for its depth.
- Take the bigger one and add 1 for this node.
Watch it run
Exampletree = [3, 9, 20, null, null, 15, 7]
Leaf 9: both children empty, depth 1 + max(0, 0) = 1.
depth(9) = 1
Where people slip
- An empty tree has depth 0, not 1; the +1 belongs to a real node only.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.