Two Sum IV - Input is a BST

Moderate

0/80

Contributed by

1 upvote

Asked in company

Problem statement

You are given a binary search tree consisting of ‘N’ nodes. Each node has a weight associated with it. Ninja recently learned about tree algorithms and the teacher wants him to know whether a pair of nodes exists whose sum of values is exactly equal to ‘K’.

Output true if such a pair exists.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’, representing the number of nodes in the tree and the sum value.

The third line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.

Example :

Consider the binary tree:-

The input of the tree depicted in the image above will be like : 
5
3 6
2 4 -1 7
-1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1
The value of the root node is 5.

Level 2 :
Left child of 1 = 2
Value of left child of 1 = 3
Right child of 1 = 3
Value of right child of 1 = 6

Level 3 :
Left child of 2 = 4
Value of left child of 2 = 2
Right child of 2 = 5
Value of Right child of 2 = 4
Left child of 3 = null(-1)
Right child of 3 = 6
Value of right child of 3 = 7

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null(-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Output format :

For each test case, output a boolean value denoting if such a pair exist.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

The weights are pair-wise distinct in the tree.

Constraints :

1 <= T <= 10
1 <= N <= 10^4
-10^4 <= value of node[i] <= 10^4
Value of node[i] is never equal to -1
It is guaranteed that the given input is a binary tree.

Time Limit: 1 sec

Sample Input 1 :

2
5 3
5 0 -1 -1 1 -1 3 2 -1 -1 -1 
5 -6
-4 -1 -3 -1 2 -2 4 -1 -1 -1 -1

Sample Output 1 :

true
true

Explanation Of Sample Input 1 :

For test case 1 we have, 

The input tree:

The pair of values {0, 3} have sum 3.

So, we output 1(true).

For test case 2 we have,

The input tree :

The pair of values {-4, -2} have sum -6.

So, we output 1(true).

Sample Input 2 :

2
4 8
4 -2 -1 -3 3 -1 -1 -1 -1 
3 4
5 0 -1 -4 -1 -1 -1

Sample Output 2 :

true
false

Console