Two nodes with given sum in binary search tree

Tags: , , , ,

Two nodes with a given sum in a binary search tree

Given a binary search tree and an integer k, find all two nodes with given sum, nodes (a,b) such that a+b =k. In other words, find two nodes in a binary search tree which add to a number. For example, in the binary search tree given below, if k = 24, node(5) and node(19) should be the result.

sum of two nodes

Two nodes with given sum in binary search tree: thoughts

We have solved a similar problem with arrays, where we had to find pairs with a given sum k, the basic idea was that if the array is sorted, we will scan it from start(moving right) and end(moving left), and see if elements at two ends add up to k. If the sum of those numbers is greater than k, we move to right from start. If the sum of those two numbers is less than k, we move to left from end. We continue till two pointers cross each other.

Is there a way in which binary search tree can be sorted array? Yes, if BST is traversed in inorder, output is in sorted order of nodes. So, if we scan the BST and store in an array, the problem is same as find pairs in an array with a given sum. 
However, the solution requires two scans of all nodes and additional space of O(n).

Another solution could be to use a hash map. Each node is stored in the hashmap and at each node, we check if there is a key (sum-node.value) present in the hashmap. If yes, then two nodes are added into the result set. This still requires additional space, however, there is only one traversal of the tree.

How can we avoid additional space? Look at the binary search tree property: all the nodes on the left subtree of a root node are less than and all the nodes on right subtree are greater than the root node.
We know that the minimum node in BST is the leftmost node and the maximum node is the rightmost node.
If we start an inorder traversal, the leftmost node is the first node to be visited and if we do a reverse inorder traversal, the rightmost node is the first node will be visited. If the sum of the minimum and the maximum is less than k, then we have to go to the second minimum (next node in forward inorder traversal). Similarly, if the sum of the minimum and the maximum is greater than k, then we have to go to the second maximum(next in reverse inorder traversal)

How can we do a forward and reverse inorder traversal at the same time? 

Sum of two nodes in binary search tree: stacks

We know how to traverse a tree using stack data structure. We will use two stacks, one stack stores the nodes to be visited in forward inorder traversal and second stores the nodes to be visited in reverse inorder traversal. When we reach the leftmost and the rightmost node, we pop from the stacks and check for equality with the given sum.
If the sum of the two nodes is less than k, we increase one of the nodes. We will go to the right subtree of the node popped from the forward inorder stack. Why? Because that’s where we will find the next greater element.

If the sum of the two nodes is greater than k, we decrease one of the nodes. We will go to the left subtree of the node popped from the reverse inorder stack. Why? Because that’s where we will find the next smaller element.

We will continue till both forward and reverse inorder traversal do not meet.

Two nodes with given sum in BST: Implementation

package com.company;

import com.company.BST.TreeNode;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 26.11.18.
 */
public class TwoNodesWithGivenSum {
    public ArrayList<Pair<Integer, Integer>>
		findPairsWithGivenSum(TreeNode root, int sum) {

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        ArrayList<Pair<Integer, Integer>> result
			= new ArrayList<>();

        TreeNode cur1 = root;
        TreeNode cur2 = root;

        while (!s1.isEmpty() || !s2.isEmpty() ||
                cur1 != null || cur2 != null) {
            if (cur1 != null || cur2 != null) {
                if (cur1 != null) {
                    s1.push(cur1);
                    cur1 = cur1.getLeft();
                }

                if (cur2 != null) {
                    s2.push(cur2);
                    cur2 = cur2.getRight();
                }
            } else {
                int val1 = (int)s1.peek().getValue();
                int val2 = (int)s2.peek().getValue();

                if (s1.peek() == s2.peek()) break;

                if (val1 +  val2 == sum)
					result.add(new Pair(val1, val2)) ;

                if (val1 + val2 < sum) {
                    cur1 = s1.pop();
                    cur1 = cur1.getRight();
                } else {
                    cur2 = s2.pop();
                    cur2 = cur2.getLeft();
                }
            }
        }

        return result;
    }
}

Test cases

package test;

import com.company.BST.BinarySearchTree;
import com.company.TwoNodesWithGivenSum;
import javafx.util.Pair;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class TwoNodesWithGivenSumTest {

    TwoNodesWithGivenSum tester = new TwoNodesWithGivenSum();

    @Test
    public void twoNodesWithGivenSumTest() {

        BinarySearchTree<Integer> binarySearchTree
			= new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        ArrayList<Pair<Integer, Integer>> result
			= new ArrayList<>();
        result.add(new Pair(12,15));

        assertEquals(result, 
			tester.findPairsWithGivenSum(
				binarySearchTree.getRoot(),
				27
			)
		);
    }

    @Test
    public void twoNodesWithGivenSumNotPossibleTest() {

        BinarySearchTree<Integer> binarySearchTree
			= new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        ArrayList<Pair<Integer, Integer>> result 
			= new ArrayList<>();
        assertEquals(result,
			tester.findPairsWithGivenSum(
				binarySearchTree.getRoot(),
				45
			)
		);
	}

    @Test
    public void twoNodesWithGivenSumNullTreeTest() {

        ArrayList<Pair<Integer,Integer>> result
			= new ArrayList<>();

        System.out.println(result);

        assertEquals(result,
			tester.findPairsWithGivenSum(
				null,
				45
			)
		);
    }
}

The complexity of this method to find two nodes with a given sum in a binary search tree is O(n). We are storing nodes in stacks, which will have space complexity of O(n), however, it is less than the previous solutions as it actually making the recursive stack explicit.

Please share if you have any doubts or something is missing or wrong. If you are preparing for an interview, signup to receive a free interview kit.