Unequal Ancestor

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.

K^th ancestor of a node V is defined as:

If K >= 1, (K-1)^th ancestor of the parent of node V.

If K = 0, the node V itself.

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  not equal to each other.

<!--

You have to find the number of nodes having their K^th ancestor value complementary to their value.

-->

Problem Constraints

1 <= N <= 10⁵

0 <= B <= 10⁵

Value of each node is either 0 or 1.

Input Format

First argument is the root node of the binary tree A.

Second argument is an integer B.

Output Format

Return the number of such ordered pairs.

Example Input

Input 1:

Input 2:

Example Output

Output 1:

Output 2:

Example Explanation

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.

Start solving Unequal Ancestor on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Unequal Ancestor

Discussion