359. Size of a Subtree
Foundation1000 ms256 MBSolved by 0%
Print how many nodes lie in the subtree rooted at the node holding value x,
counting that node itself. Print 0 if no node holds that value.
Two steps: find the node, then count everything beneath it. Both are traversals you have already written, and the only new idea is that the second one starts somewhere other than the root.
Counting the starting node itself is the part to get right. A subtree of a leaf has size 1, not 0.
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.
Output
Print one integer, the number of nodes in that subtree, or 0 if x is absent.
Input7 4
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output7
Noteis the root, whose subtree is the whole tree
Input7 7
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output1
Noteis a leaf, whose subtree is itself and has size 1 rather than 0
Input7 999
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output0
Noteis absent from the tree
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution