352. How Deep Is a Value
Foundation1000 ms256 MBSolved by 0%
Print the depth of the node holding value x, counting the root as depth 1.
Print -1 if no node holds that value.
Values are distinct, so there is at most one answer.
Carry a depth down as you walk, and stop when you find it. A -1 for absent is
a deliberate choice: it is a value no real depth can take, so the caller can
always tell the two cases apart.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value, x ≤ 1000000000` - All values are distinct. - The input always forms a valid tree rooted at node 1.
Input
The first line contains two integers n and x.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root at depth 1.
Output
Print the depth of the node holding x, or -1 if there is none.
Input7 4
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output1
Noteis the root, whose depth is 1 rather than 0
Input7 7
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output3
Noteis a leaf in the bottom row
Input7 999
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output-1
Noteis absent, so the answer is -1 rather than 0
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.