Find a pair with given sum in a BST

Given a binary search tree, find a pair with given sum present in it.

 

For example, consider below BST. If given sum is 14, the pair is (8, 6)


 
Pair with given sum in BST

 


 

1. Hashing

This problem can be easily solved using hashing. We traverse the tree in inorder fashion and insert every node’s value into a set. We also check if for any node, the difference between given sum and node’s value is found in set, then the pair with given sum exists in the tree.

C++

Download   Run Code

Output:

Pair found (12, 16)

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 


 

2. Space Optimized solution

We can solve this problem without using extra space by simultaneously traversing the tree both inorder and reverse inorder by maintaining two pointers. Then the problem can be solved in similar way as sorting approach discussed here i.e. if the sum of current nodes is less than the required sum, we move to next node in normal inorder traversal, else if their sum is more than the required sum we move to next node in reverse inorder traversal. If the current sum becomes equal to the required sum, then the pair is found in BST and we return true.

C++

Download   Run Code

Output:

Pair found (8, 20)

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz