Find two numbers in a binary search tree that add

Question

You are given a BST of numbers. You have to find two numbers (a, b) in it such that a + b = S, in O(n) time and O(1) space.

What could be the algorithm?

One possible way could be two convert the BST to a doubly linked List and then start from the front and end:

if front + end > S then end--

Or:

if front + end < S then front++

Answer 1

I was asked this question in an interview recently. When I was stuck, I was given a hint.

Hint: Let's say you need to solve this same problem for a sorted array, how would you solve it then.

Me: Keep two pointers. One at the beginning, another at the end. If the sum of elements at those pointers is less than the required sum, move the front pointer towards right, else move the back pointer towards left.

Interviewer: How could you do the same thing for a binary search tree?

Me: Do an in-order traversal, and save the pointers to nodes in an array. And use the same logic as in the case of arrays.

Interviewer: Yes, that works. But the space complexity is O(n). Could you reduce it?

Me (after a lot of time): Ok, convert the BST in a doubly linked list, using this algo. And then use the same logic as in the case of array. Space comlexity will be O(lg(n)) due to recursion.

Answer 2

Try as I could, I'm not sure this is possible with a binary tree that has no parent pointers. O(1) space means you can neither use recursion (the stack growth is O(log n)) nor copying to a doubly linked list (O(n)).

The method you allude to is an O(n) time complexity solution but not with a normal binary tree. In fact, I answered a similar question in great detail here. That was solved with O(n) space but only because they weren't initially sorted.

It is possible with a tree containing parent pointers. If the child nodes have pointers to their parents, you can basically treat the tree as a doubly-linked list processed iteratively.

To do that, you run the start pointer down to the leftmost node and the end pointer down to the righmost node. You also maintain two variables to store the last movement (up or across, initially up) of each pointer so you can intelligently select the next move (the front++ and end-- in your question).

Then you can use the current pointers and last movements, along with the current sum, to decide which pointer to move (and how).

Answer 3

As others mentioned, you can't solve this in constant O(1) space. Furthermore, all the other solutions currently suggested use at least O(log^2 n) space, not O(log n) space: the stack has O(log n) frames and each frame has a O(log n) sized pointer.

Now, the currently accepted solution by @dharm0us destroys the BST by converting it into an array. This is unnecessary. Instead, use two iterators, one doing an in-order traversal and one doing a reverse-order traversal, and look for two numbers the same as you would in an array. Each iterator has a stack with O(log n) frames with each frame holding a O(log n) size pointer for total space O(log^2 n). The time is clearly linear O(n).