Maximum Depth of Binary Tree

Easy#104tree nodes

You get the root of a binary tree. Find its depth: how many nodes lie on the longest path from the root down to a leaf. Our tree: 11 with children 4 and 8; 8 has children 2 and 13; 2 has a left child 6 — the answer is 4: the path 11 → 8 → 2 → 6.

104 Maximum Depth of Binary TreeWalkthrough · 1×

Example: find the depth of a lopsided binary tree: the first leaf is shallow, the deepest one is far to the right.

nonenonenonenonenonenonenone11482136call stacktop on the right11
not visited yetwaiting on the call stackcurrent callreturned, ↑ its depthnone: an empty child

11 is a node, not none

01/43
restart · back · play · step
Speed
1function maxDepth(node):
2 if node is none:
3 return 0
4 left = maxDepth(node.left)
5 right = maxDepth(node.right)
6 return 1 + max(left, right)
state
node
11
left
–
right
–
click a step to go back

← → step · space play/pause

Why it works

  1. The depth of a tree is its root plus the depth of its deeper subtree, and each subtree is a smaller tree of the same kind, so one call per node answers it.
  2. A node returns only after both of its sides have answered, so the first leaf found, 4, never decides alone: the root compares 1 with 3.
  3. An empty child returns 0, which makes a leaf 1 + max(0, 0) = 1 with no special case.

Complexity

Time O(n): one call per node, plus one per empty child. Memory O(h), where h is the height of the tree: the call stack holds one path from the root.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.