Wildlife Corridor Boundary
Maximum nodes on a binary tree path with at most one value change
A wildlife survey's observation stations form a binary tree. Each station stores an integer habitat code in its node value. Equal codes represent the same habitat type, even if the stations are far apart.
A corridor is a nonempty simple path through the tree: consecutive stations are connected by a parent-child edge, and no station is visited twice. The path may start and end anywhere; it does not have to pass through the root.
An edge is a habitat boundary when its two endpoint stations have different habitat codes. A corridor is acceptable if it crosses at most one habitat boundary.
Return the largest number of stations in an acceptable corridor. Return 0 if the tree is empty.
Examples
Example 1
Input: root = [4,4,9,4,4] Output: 4
The path from the leftmost leaf through its parent and the root to the right child contains four stations. Its habitat codes are 4, 4, 4, and 9, so it crosses only one boundary.
Example 2
Input: root = [1,2,3,4,5] Output: 2
Every edge joins different habitat codes. Any path with three stations would cross two boundaries, so an acceptable corridor can contain at most two stations.
Example 3
Input: root = [7,7,7,7,null,null,7] Output: 5
All stations have the same habitat code. The longest leaf-to-leaf path is acceptable without crossing any boundary.
Constraints
- The tree contains between 0 and 4,000 nodes.
- -1,000,000,000 <= node.val <= 1,000,000,000.
- The input is a valid binary tree, supplied as a level-order list with null for missing children.
Count stations, not edges. Habitat codes are labels: their numerical distance has no meaning. An iterative traversal avoids recursion-depth issues on a long chain. The intended solution takes O(n) time and O(n) auxiliary space.
Hints
Show hint 1Hint 1
For each node, track the longest downward path starting there with zero boundaries and with at most one boundary.
Show hint 2Hint 2
A path whose highest node is the current node can use one arm from each child, but the two arms must share a total boundary budget of one.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you recover the endpoints of an optimal corridor, with a deterministic tie-breaking rule?
- How would the dynamic programming change if a corridor could cross at most k habitat boundaries?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem