A mountaineering expedition sets up a chain of relay camps below a single basecamp. Every established camp may found at most two further forward camps -- a left-flank camp and a right-flank camp -- each of which may in turn found up to two more camps, and so on down the mountain. Given the full layout of camps founded from the basecamp, determine the greatest number of camps that appear along any single unbroken chain running from the basecamp down to one of its terminal (childless) camps.
A single line containing the camp layout in preorder form: a sequence of space-separated tokens where each token is either the literal null or an integer camp id. Reading the tokens left to right, recursively:
null denotes that no camp was founded at this position.null, meaning no basecamp was ever established.Print a single integer: the greatest number of camps along any unbroken chain from the basecamp to a terminal camp, counting the basecamp itself. Print 0 if no basecamp was established.
Example 1
Input
3 9 null null 20 15 null null 7 null null
Expected
3
Explanation
The preorder stream builds a basecamp with id 3, whose left-flank camp has id 9 and founds no further camps, and whose right-flank camp has id 20; camp 20's left-flank camp has id 15 and its right-flank camp has id 7, neither founding further camps. The longest chain is basecamp(3) -> camp(20) -> camp(15 or 7), which has 3 camps, so the answer is 3.
Example 2
Input
42 null null
Expected
1
Explanation
Only a single basecamp with id 42 is established, founding no further camps, so the longest chain has exactly 1 camp.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →