Find two numbers from BST which sum to given number K

Question

Given a BST with unique integers and a number K. Find a pair ( a, b ) in BST such that a + b = k.

Constraints:

You cannot change the structure of the tree, otherwise we could have converted it to sorted Doubly linked list and foiund the pair in O(N).

The approach should be in-place.

O(N) solution is needed.

I have thought of something related to running two pointers, one from left to right and the other from right from to left in the same way we do in case of finding pair in a sorted array. But, i could not get a clear picture of how to implement it?

Answer 1

As Samuel already said I also think your solution should work. Two pointers or iterators, one from left to right (small to big) and one from right to left (big to small). If (a + b) > k then iterate the right to left one (the next smaller value) else the other one (the next bigger value). You can stop if a >= b The runtime is linear even in case of unbalanced tree. Every node is visited max one time.

I think real function recursion will become somewhat complicated in this case. So better use two selfmade stacks to do the recursion in one function. Something like that:

a = b = root;
while (a.left) {
    astack.push(a)
    a = a.left
}
while (b.right) {
    bstack.push(b)
    b = b.right
}


while (a.value < b.value) {
    if (a.value + b.value == k) found!
    if (a.value + b.value < k) {
        if (a.right){
            a = a.right
            while (a.left) {
                astack.push(a)
                a = a.left
            }
        } else a = astack.pop()
    } else {
        if (b.left){
            b = b.left
            while (b.right) {
                bstack.push(b)
                b = b.right
            }
        } else b = bstack.pop()
    }
}

Answer 2

I agree the 2 pointer approach will work. I did think of the same thing. However, I think the code will get super complicated/messy if we try to use recursion. The other approach is to use stacks as the top rated answer mentions. However, if we have to use space to make it less complex, we can totally avoid the 2 pointer approach.

I have used a different approach here. Traverse the tree in any order you want and insert the elements in a HashSet. Once this set is populated, iterate through the elements of set and just check if the difference between the target_sum and current number exists. if it does return or else move to next element.

This is still order of O(n) approach but uses O(n) and much simpler to understand in my opinion.

Answer 3

We traverse BST in Normal Inorder and Reverse Inorder simultaneously. In reverse inorder, we start from the rightmost node which is the maximum value node. In normal inorder, we start from the left most node which is minimum value node. We add sum of current nodes in both traversals and compare this sum with given target sum. If the sum is same as target sum, we return true. If the sum is more than target sum, we move to next node in reverse inorder traversal, otherwise we move to next node in normal inorder traversal. If any of the traversals is finished without finding a pair, we return false.

   boolean isPairPresent(Node3 root, int sum) 
   {
    Stack<Node3> stack1 = new Stack<Node3>();
    Stack<Node3> stack2 = new Stack<Node3>();

    boolean done1 = false;
    boolean done2 = false;

    int val1 = 0, val2 = 0;
    Node3  curr1 = root, curr2 = root;

    while(true) {

        while(done1 == false)   {
            if(curr1 != null)   {
                stack1.push(curr1);
                curr1 = curr1.left;
            } else {
                if(stack1.isEmpty())
                    done1 = true;
                else    {
                    curr1 = stack1.pop();
                    val1 = curr1.data;
                    curr1 = curr1.right;
                    done1 = true;
                }
            }   
        }

        while(done2 == false)   {
            if(curr2 != null)   {
                stack2.push(curr2);
                curr2 = curr2.right;
            } else {
                if(stack2.isEmpty())
                    done2 = true;
                else {
                    curr2 = stack2.pop();
                    val2 = curr2.data;
                    curr2 = curr2.left;
                    done2 = true;
                }
            }
        }

        if((val1 != val2) && (val1+val2 == sum))    {
            System.out.println("Pair found: "+val1+" + "+val2+" = "+sum);
            return true;
        } else if(val1 + val2 > sum) {
            done2 = false;
        } else if(val1 + val2 < sum)
            done1 = false;

        if(val1 >= val2)
            return false;
    }
}