Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
The simplest solution will be to traverse over the whole tree and consider every possible pair of nodes to determine if they can form the required sum . But, we can improve the process if we look at a little catch here.
If the sum of two elements equals , and we already know that exists in the given tree, we only need to check if an element exists in the given tree, such that . Based on this simple catch, we can traverse the tree in both the directions(left child and right child) at every step. We keep a track of the elements which have been found so far during the tree traversal, by putting them into a .
For every current node with a value of , we check if already exists in the array. If so, we can conclude that the sum can be formed by using the two elements from the given tree. Otherwise, we put this value into the .
If even after the whole tree's traversal, no such element can be found, the sum can't be formed by using any two elements.
Complexity Analysis
Time complexity : . The entire tree is traversed only once in the worst case. Here, refers to the number of nodes in the given tree.
Space complexity : . The size of the can grow upto in the worst case.
Algorithm
In this approach, the idea of using the is the same as in the last approach. But, we can carry on the traversal in a Breadth First Search manner, which is a very common traversal method used in Trees. The way BFS is used can be summarized as given below. We start by putting the root node into a . We also maintain a similar to the last approach. Then, at every step, we do as follows:
Remove an element, , from the front of the .
Check if the element already exists in the . If so, return True.
Otherwise, add this element, to the . Further, add the right and the left child nodes of the current node to the back of the .
Continue steps 1. to 3. till the becomes empty.
Return false if the becomes empty.
By following this process, we traverse the tree on a level by level basis.
Complexity Analysis
Time complexity : . We need to traverse over the whole tree once in the worst case. Here, refers to the number of nodes in the given tree.
Space complexity : . The size of the can grow atmost upto .
Algorithm
In this approach, we make use of the fact that the given tree is a Binary Search Tree. Now, we know that the inorder traversal of a BST gives the nodes in ascending order. Thus, we do the inorder traversal of the given tree and put the results in a which contains the nodes sorted in ascending order.
Once this is done, we make use of two pointers and pointing to the beginning and the end of the sorted . Then, we do as follows:
Check if the sum of the elements pointed by and is equal to the required sum . If so, return a True immediately.
Otherwise, if the sum of the current two elements is lesser than the required sum , update to point to the next element. This is done, because, we need to increase the sum of the current elements, which can only be done by increasing the smaller number.
Otherwise, if the sum of the current two elements is larger than the required sum , update to point to the previous element. This is done, because, we need to decrease the sum of the current elements, which can only be done by reducing the larger number.
Continue steps 1. to 3. till the left pointer crosses the right pointer .
If the two pointers cross each other, return a False value.
Note that we need not increase the larger number or reduce the smaller number in any case. This happens because, in case, a number larger than the current is needed to form the required sum , the right pointer could not have been reduced in the first place. The similar argument holds true for not reducing the smaller number as well.
Complexity Analysis
Time complexity : . We need to traverse over the whole tree once to do the inorder traversal. Here, refers to the number of nodes in the given tree.
Space complexity : . The sorted will contain elements.
Analysis written by: @vinod23