Find two numbers in a binary search tree that add up to a third number

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.