How Deep the Cave Goes
A caving club has mapped a cave. From the entrance chamber, at most two tunnels lead further down, and the same is true in every chamber below. Tunnels never join up again, so the map is a binary tree. Each chamber has a number painted on the wall.
Before the next trip, the club needs to know how many chambers the longest descent passes through, counting the entrance and the last chamber. That decides how many rope anchors to pack.
Your task
Write caveDepth(root). Return the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0, and a tree with only a root has depth 1.
Trees are shown in level order, like [1, 2, 3, null, 4], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
caveDepth(root: TreeNode) → int
Examples
root = [1, 2, 3, null, 4, 5, null, null, null, 6]
4
From the entrance 1, the left tunnel goes 1 → 2 → 4 (3 chambers). The right tunnel goes 1 → 3 → 5 → 6 (4 chambers). The deepest descent passes 4 chambers. Following only the left tunnels would wrongly give 3.
root = [8]
1
A cave with just the entrance chamber. The answer counts chambers, not tunnels, so it is 1, not 0.
Constraints
- 0 ≤ number of chambers ≤ 1,000
- -1,000 ≤ chamber number ≤ 1,000
- The tree is at most 500 levels deep.
Start with brute force
List every route from the entrance to a dead end, count the chambers on each, and keep the largest count.
That works, but if you store each route as you go you copy paths over and over: a cave with 1,000 chambers in a long chain makes routes of up to 1,000 chambers each. You do not need the routes at all, only their lengths, and each chamber can compute its own depth from its children's answers in one visit.
Hints
0 of 4 shown- Hint 1
Stand in chamber 3 of the first example and ignore everything above it. How deep is the cave below you, counting chamber 3 itself?
- Hint 2
The depth from any chamber is 1 (the chamber itself) plus the depth of the deeper of its two sub-caves. You do not know which side is deeper until you have measured both.
- Hint 3
That definition calls itself on smaller trees. What is the answer for a tunnel that leads nowhere, an empty tree?
- Hint 4
Recursion: if the node is null, return 0. Otherwise return
1 + max(depth(left), depth(right)). Each chamber asks its two children and passes the bigger answer, plus one, up to its parent.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every chamber is the entrance of a smaller cave. So the depth of a cave is one chamber plus the depth of its deeper sub-cave, and an empty tunnel has depth 0.
Trace [1, 2, 3, null, 4, 5, null, null, null, 6], answering from the bottom up:
- Chambers 4 and 6 have no tunnels below. Each returns
1 + max(0, 0) = 1. - Chamber 5 has only 6 below it:
1 + max(1, 0) = 2. - Chamber 2 has only 4 below it (on the right):
1 + max(0, 1) = 2. - Chamber 3 has only 5 below it:
1 + max(2, 0) = 3. - The entrance 1 compares its sides:
1 + max(2, 3) = 4.
No chamber is visited twice, and nobody stores a route. Each call only returns one number to its parent.
function caveDepth(root) {
if (root === null) return 0; // no chamber, no depth
const left = caveDepth(root.left);
const right = caveDepth(root.right);
return 1 + Math.max(left, right);
}def cave_depth(root):
if root is None: # no chamber, no depth
return 0
left = cave_depth(root.left)
right = cave_depth(root.right)
return 1 + max(left, right)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.