# 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) #### 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++

Output:

Pair found (12, 16)

## Java

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++

Output:

Pair found (8, 20)

## Java

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.     (5 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Abhishek Sharma

Solution 2 is wrong.
For the array {7, 10, 9, 20}, pair_sum = 40, it returns true
https://ideone.com/8qqGP8 Guest

solution 2 is extremely wrong,you can try with this [ 15, 11, 8, 6, 9, 12,25, 20, 18, 21, 30] and sum=30
output: pair don’t exist