Two Sum IV - Input is a BST

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
Cars24

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
Hint

For faster value lookup, you can store the value in some data structures like map/set.

Approaches (2)
HashSet
  1. We have to find such pair of nodes(i and j, where i != j) in tree such that valNode[i] + valNode[j] = K.
  2. Rewriting the above equation as valNode[i] = K - valNode[j].
  3. So if we have a node i of value valNode[i] then we only need to search for the node of value K - valNode[j].
  4. We can optimize the search by storing the values in unordered_set while traversing the tree.
  5. After storing we just iterate on the elements of unordered_set and find K-valNode[j].
     

The steps are as follows : 

  1. Create an unordered_set.
  2. Traverse the tree using inorder traversal and insert the values in the unordered_set.
  3. Iterate over the elements of unordered_set :
    • For each element (x) search for K-x.
    • If found return true.
  4. After iterating over all elements if no pair is found return false.
     
Time Complexity

O( N ), where ‘N’ is the number of vertices in the tree.

 

We are traversing the tree once and storing the values in unordered_set which takes ~N operations and searching in unordered_set takes ~1. 

Hence the overall time complexity is O( N ).

Space Complexity

O( N ), where ‘N’ is the number of vertices in the tree.

 

Storing the values of the tree takes ~N space. 

Hence, the overall Space Complexity is O( N ).

Code Solution
(100% EXP penalty)
Two Sum IV - Input is a BST
Full screen
Console