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

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).