Last Updated: 31 Dec, 2020

Two Sum IV - Input is a BST

Moderate

Asked in companies

Solve now

Problem statement

You have been given a Binary Search Tree and a target value. You need to find out whether there exists a pair of node values in the BST, such that their sum is equal to the target value.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a value greater than all the values keys in the node's left subtree and less than those in its right subtree.

Follow Up:

Can you solve this in O(N) time, and O(H) space complexity?

Input format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow. 

The first line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. 

The second line of each test case contains a single integer representing the target value.

For example, the input for the tree depicted in the below image would be :

bst_example

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = 2
Right child of 4 = 6

Level 3 :
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4 :
Left child of 1 = null (-1)
Right child of 1 = null (-1)
Left child of 3 = null (-1)
Right child of 3 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = 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).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:    
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1

Output format:

For each test case, print True or False in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 3000
-10^9 <= node data <= 10^9, (where node data != -1)
-10^9 <= target value <= 10^9

Where N denotes is the number of nodes in the given tree.

Time Limit: 1 second

Solve now

Approaches

01 Approach

The idea is to traverse the BST in a level-order manner and let’s denote the value of the current node as A. For each node, check whether the node with value (target - A) is present in the BST or not. We can search this node in the given tree using the BST property, i.e. at any node we go to left subtree or right subtree by comparing the node value to (target - A), and if the value is found in the BST, return true. If the value is not found for any node, return false.

Solve now

02 Approach

In the previous approach, for each node in the BST, we were searching for a second node with the value (target - value of the current node) again and again. We can optimize this search by using a HashSet to keep track of the elements of the BST. So we will traverse the tree in a depth-first manner, and for any current node of value A, we check if there is a value present in the HashSet which is equal i.e. target - A. If so, we can say that there are two nodes with the values such that their sum is equal to target, Otherwise, we put the value to the HashSet.

Steps:

Create an empty HashSet let’s say st to store the values of the nodes of the BST.
we create a recursive function that traverses each node in the given tree to check the pair sum:
If root == null, then return false.
If st contains the target - root.data then return true.
Else add root.data to st.
If any of the subtrees either left or right returns true then return true.
Else return false.

Solve now

03 Approach

We can use the property of the inorder traversal of the BST i.e. inorder traversal of a BST always traverses the nodes in increasing order of their values. So, we perform inorder traversal on the BST and store the values in an auxiliary array. As this array is sorted, so now we can use the two-pointer technique on this sorted array for determining if two elements exist in the array which sums up to the target value.

Steps:

Create an empty array let’s say inorderArray to store the values of BST in the inorder traversal.
Create an inorder function and pass the root and inorderArray as two arguments and store the value of each node in the array.
Then take two pointers let’s say i and j, where i points to the start of the array and j points to the end of the array.
Run a loop, while i < j, and do:
1. Add the value of inorderArray[i] and inorderArray[j]. If this sum equals the target value, we return true.
2. If the sum is greater than the target value, then decrease j by 1.
3. Else increase i by 1.
At last, if there is no pair then we return false.

void inorder(root, inorderArray):

Until all the nodes are traversed
1. Recursively traverse the left subtree.
2. Add the current node’s value to the inorderArray.
3. Recursively traverse the right subtree.

Solve now

04 Approach

The idea is the same as the previous approach with space optimization, by applying the two-pointer technique on the given BST. In this approach, we will maintain a forward and a backward iterator that will iterate the BST in the order of in-order and reverse in-order traversal respectively using the two stacks, one maintaining the leftmost value of the BST, start, and one maintaining the rightmost value of BST, end. Now, using the two-pointer technique, we check if the sum of values at the start and end nodes are equal to the target. If they are equal to the target value, then return true. If the values are lesser than the target value, we make forward iterator point to the next element using stack, else if the values are greater than the target value, we make backward iterator point to the previous element using the second stack.

At last, if we find no such two elements, then return false.

Steps:

Create two empty stacks start and end to store the nodes in normal inorder and reverse inorder traversal respectively.
Take a node let’s say currNode and make it point to the root.
While the currNode is not NULL, do:
1. Push the currNode to start stack.
2. currNode = currNode->left.
After the loop is over, make currNode point to root again and while the currNode is not NULL, do:
1. Push the currNode to end stack.
2. currNode = currNode->right.
While the top element of both the stacks are not equal, do:
1. Create two variables val1 and val2 to store the top element of the stack start and end respectively.
2. If the sum of val1 and val2 is equal to the target, then return true.
3. If the sum of val1 and val2 is less than the target, then make the currNode point to the right child of the top element of the start stack and pop this node.
4. While the currNode is not NULL, do:
  1. Push the currNode to start stack.
  2. currNode = currNode->left.
5. Else if the sum of val1 and val2 is greater than the target, then make the currNode point to the left child of the top element of the end stack and pop this node.
6. While the currNode is not NULL, do:
  1. Push the currNode to the end stack.
  2. currNode = currNode->right.
Finally, return false, if we come out of the loop.

Solve now