Longest Museum Stroll
A small museum is a maze of rooms joined by doorways. From the entrance hall, at most two doorways lead to further rooms, and each of those rooms leads to at most two more. There are no loops, so the floor plan is a binary tree with the entrance hall at the root. Each room has a number.
A fitness app wants to advertise the museum's longest stroll: the longest walk between any two rooms that never goes through the same doorway twice. The walk does not have to start at the entrance, and it may go up toward the entrance and back down a different branch.
Your task
Write longestStroll(root). Return the number of edges (doorways) on the longest path between any two nodes of the tree. The path does not need to pass through the root.
An empty tree and a tree with one node both return 0. Trees are shown in level order, like [1, 2, 3], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
longestStroll(root: TreeNode) → int
Examples
root = [2, 1, null, 3, 4, 5, null, null, 6, 7]
5
The longest stroll is 7 → 5 → 3 → 1 → 4 → 6: five doorways. It turns around at room 1 and never visits the entrance hall 2. A stroll from the entrance can only reach 4 doorways (2 → 1 → 3 → 5 → 7).
root = [1, 2, 3]
2
Walk 2 → 1 → 3. That visits 3 rooms but passes only 2 doorways, and the answer counts doorways.
Constraints
- 0 ≤ number of rooms ≤ 1,000
- -1,000 ≤ room number ≤ 1,000
- The tree is at most 500 levels deep.
Start with brute force
For every room, run a search to find the farthest room from it, and keep the largest distance found. Or, for every room, compute the depth of its two subtrees from scratch and add them.
Both are O(n²): each of up to 1,000 rooms starts a walk that can touch all 1,000 rooms. The repeated work is the subtree depths. A room's depth is needed by its parent too, so compute each depth once, bottom-up, and check the turning point while you are there.
Hints
0 of 4 shown- Hint 1
Every path in a tree has one highest room, where it stops going up and starts going down. In the first example, which room is the turning point of the longest stroll?
- Hint 2
If a path turns at room X, it goes as far down as possible on X's left side and as far down as possible on X's right side. So its length is (depth of left subtree) + (depth of right subtree), counted in doorways from X.
- Hint 3
You do not know which room is the best turning point, so try every room. Can one bottom-up walk give you both subtree depths at every room without recomputing them?
- Hint 4
Write a depth function that returns
1 + max(left, right)(0 for null), and inside it, before returning, update a sharedbest = max(best, left + right). The depth function's return value goes to the parent;bestis the answer.
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 path has one highest room where it turns. If the path turns at room X, its best length is the depth of X's left subtree plus the depth of its right subtree. Those depths count rooms, and the number of rooms below X on a side equals the doorways from X down that side, so the sum is already in doorways.
Trace [2, 1, null, 3, 4, 5, null, null, 6, 7], bottom-up:
- Rooms 7 and 6 are leaves: depth 1, turning there gives 0 + 0 = 0.
- Room 5 has only 7 below: depth 2, turning gives 1 + 0 = 1.
- Room 3 has only 5 below: depth 3, turning gives 2 + 0 = 2. Room 4 has only 6 below: depth 2, turning gives 0 + 1 = 1.
- Room 1 has depth 3 on the left and 2 on the right: turning gives 3 + 2 = 5. Best is now 5.
- Room 2 (the entrance) has depth 4 on the left and 0 on the right: 4 + 0 = 4. Best stays 5.
The function returns one thing (depth) but records another (best). Mixing them up is the usual bug: the parent needs the depth, not the best path.
function longestStroll(root) {
let best = 0;
// Returns the depth of a subtree, counted in rooms.
function depth(node) {
if (node === null) return 0;
const left = depth(node.left);
const right = depth(node.right);
best = Math.max(best, left + right); // path turning at this room
return 1 + Math.max(left, right);
}
depth(root);
return best;
}def longest_stroll(root):
best = 0
# Returns the depth of a subtree, counted in rooms.
def depth(node):
nonlocal best
if node is None:
return 0
left = depth(node.left)
right = depth(node.right)
best = max(best, left + right) # path turning at this room
return 1 + max(left, right)
depth(root)
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.