340. How Many Nodes at Depth K
Foundation1000 ms256 MBSolved by 0%
Print how many nodes sit at depth k, counting the root as depth 1.
If the tree is shallower than k, print 0 rather than treating it as an error.
Carry a depth down as you walk, count the node when the depth matches, and stop descending past it since nothing deeper can help.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains two integers n and k.
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 one integer, the number of nodes at depth k.
Input7 3
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output4
Notecounts a full bottom row
Input7 1
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 alone, since depth counts from 1
Input7 4
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output0
Noteis deeper than the tree, so the answer is 0 rather than an error
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.