Given a binary search tree and an integer ‘K’, find all pairs of nodes (a,b) which sum equal to K, i.e. a+b =K. In other words, find two nodes in binary search tree which have sum equal to a number. For example, if given tree as per below and sum to be found is 60 , then output should be : (15,45) and (20,40)
This is a typical example of using binary tree property that all nodes on the left side of root are less than and all on right are greater than it.
How can we use that? Simple idea is to find left most (minimum element in tree) and right most (maximum element in tree). Now add them up. If they add up to given number, this is a pair to be added in output.
If they don’t add up, there are two cases:
1. Sum is less then given number
In this case, increase smaller number by getting inorder successor of node.
2. Sum is greater than given number
In this case, decrease bigger number by finding inorder predecessor of larger node. Problem reduced to finding inorder predecessor and successor of a node in binary search tree.
Find two nodes with sum K in BST
This method has a limitation that we have to find either predecessor or successor of a node every time nodes do not add up to given sum. These processing complexity is O(N) and for each pair we have to do it.
We can avoid this by traversing the tree first in inorder and storing all elements. This will give us a sorted array. Now use the same algorithm, with two indices i and j, i moving from 0 to N-1 and j from N-1 to 0.
Add numbers at index i and j. If sum is smaller, increment i else decrement j. If sum is equal to given number, just add pair to output.
This method requires extra space of order O(N), however, processing also requires only O(N) operations.
Please share if you find something wrong or missing. If you want to solve a specific code please do so in comments. I will put in post with proper credits.