350. Value at the Deepest Leaf
Print the value of the deepest leaf. If several leaves share the greatest depth, print the leftmost of them.
The tie rule is what makes this a single well-defined answer, and it is why a level-order walk suits the problem: the last row reached is the deepest, and the FIRST node encountered in it is the leftmost.
Push the left child before the right one, keep overwriting the answer whenever a strictly greater depth appears, and the tie resolves itself.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the value at the deepest leaf, leftmost on a tie.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.