Find if sum of two nodes is equal to a given number in BST

Problem Statement:

Given a Binary Search Tree(BST) T, where each node contains a positive integer, and an integer K, you have to find whether or not there exist two different nodes A and B such that A.value + B.value = K.
Return 1 to denote that two such nodes exist. Return 0, otherwise.

Notes 
- Your solution should run in linear time and not take memory more than O(height of T).
- Assume all values in BST are distinct.

Example :

Input 1: 

T :       10

            / \

          9   20

K = 19

Return: 1

Input 2: 

T:        10

           / \

         9   20

K = 40

Return: 0


Solution Approach:

The idea is similar to the problem of finding a pair of elements in a given array which sum up to a given number. To solve this problem, we can sort the array in ascending order and use two pointer - one pointing to start and another pointing to the end of the array. Now, if the sum of the two elements pointed by these indexes is less than the given number- increment the lower index. However, if the sum is greater than the given number - decrement the end index. The code might look like this:

boolean searchNumArray(int[] arr, int num) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == num) {
            return true;
        } else if (sum > num) {
            right--;
        } else {
            left++;
        }
    }
    return false;

The same approach can be applied to BST. If we traverse a Binary Search Tree (BST) in inorder fashion, we end up with an ascending order of the elements in the tree. So, we can dump the BST in inorder fashion into an array and then use the above program to find out the resultant nodes. But, that requires an extra space of O(n). Can we do better ?

If you observe closely - traversing a BST in reverse-inorder fashion gives us a sorted array in non-ascending order. By reverse-inorder traversal I mean traversing the BST in following order:

rev_inorder(root->right);
// Print root
rev_inorder(root->left);

Now, we can use the two-pointer approach, with one pointer moving according to the inorder traversal, while the other moving according to the reverse-inorder traversal. Which essentially means that one pointer is pointing to the smallest element of the set, while the other is pointing to the largest element in the set. At every step, we can sum these two elements and compare that with the given number. If the sum of these two elements is less than the required number, we need to move to the next element in the inorder traversal (next larger element in the ascending order). If the sum is greater than the required number, we need to move the next element in the reverse inorder traversal (next smaller element in the descending order). If the sums are equal - voila ! we are done.

Another important point to note here is that - we need to break the loop when the next node in the inorder traversal is same as the next node in the reverse inorder traversal. Following is a complete JAVA solution for the same:

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int t2Sum(TreeNode A, int B) {
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();
        TreeNode cur1 = A;
        TreeNode cur2 = A;
        
        while (!stack1.isEmpty() || !stack2.isEmpty() ||
                cur1 != null || cur2 != null) {
            if (cur1 != null || cur2 != null) {
                if (cur1 != null) {
                    stack1.push(cur1);
                    cur1 = cur1.left;
                }
                
                if (cur2 != null) {
                    stack2.push(cur2);
                    cur2 = cur2.right;
                }
            } else {
                int val1 = stack1.peek().val;
                int val2 = stack2.peek().val;
                
                if (stack1.peek() == stack2.peek()) break;
                
                if (val1 +  val2 == B) return 1;
                
                if (val1 + val2 < B) {
                    cur1 = stack1.pop();
                    cur1 = cur1.right;
                } else {
                    cur2 = stack2.pop();
                    cur2 = cur2.left;
                }
            }
        }
        
        return 0;
    }
}


- Happy Programming !!

comments powered by Disqus