Problem Description
You are given a binary tree having N nodes and having root node A. Each node in the tree has either 0 or 1 value.
Kth ancestor of a node V is defined as:
For a given integer B, You have to find the number of ordered pair of nodes (X, Y) such that node X is the B th ancestor of node Y and values of nodes X and Y are <!--complementary--> not equal to each other.
<!--You have to find the number of nodes having their Kth ancestor value complementary to their value.
-->1 <= N <= 105
0 <= B <= 105
Value of each node is either 0 or 1.
First argument is the root node of the binary tree A.
Second argument is an integer B.
Return the number of such ordered pairs.
Input 1:
1
/ \
0 0
/
1
B = 1
Input 2:
1
/ \
0 0
/ \
1 0
/ \
1 1
B = 2
Output 1:
3
Output 2:
3
Explanation 1:
values: 1 node numbers: 1 / \ / \ 0 0 2 3 / / 1 4 Ordered node pairs (1, 2) , (1, 3) and (2, 4) are desired pairs.
Explanation 2:
values: 1 node numbers: 1
/ \ / \ 0 0 2 3 / \ / \ 1 0 4 5 / \ / \ 1 1 6 7 Ordered node pairs (1, 4) , (2, 6) and (2, 7) are desired pairs.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.