Zenefits Interview - A pair with given sum in a Balanced BST

Find two elements in balanced BST which sums to a given a value. Constraints Time O(n) and space O(log n).

 

The Brute Force Solution is to consider each pair in BST and check whether the sum equals to X. The time complexity of this solution will be O(n^2).

 

A Better Solution is to create an auxiliary array and store Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted data. Once we have the Inorder traversal, we can pair in O(n) time. This solution works in O(n) time, but requires O(n) auxiliary space.

 

The idea is same as finding the pair in sorted array. 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. Following is Java implementation of this approach.

 

public int[] findPair(TreeNode root, int target) {
	int[] pair = new int[]{-1, -1};
	Stack<TreeNode> leftStack = new Stack<>();
	Stack<TreeNode> rightStack = new Stack<>();
	boolean searchLeft = true, searchRight = true;
	TreeNode leftNode = root, rightNode = root;
	int leftVal = 0, rightVal = 0;
	while(true) {
		while(searchLeft) {
			if(leftNode != null) {
				leftStack.push(leftNode);
				leftNode = leftNode.left;
			} else {
				searchLeft = false;
				if(!leftStack.isEmpty()) {
					leftNode = leftStack.pop();
					leftVal = leftNode.val;
					leftNode = leftNode.right;
				}
			}
		}
		while(searchRight) {
			if(rightNode != null) {
				rightStack.push(rightNode);
				rightNode = rightNode.right;
			} else {
				searchRight = false;
				if(!rightStack.isEmpty()) {
					rightNode = rightStack.pop();
					rightVal = rightNode.val;
					rightNode = rightNode.left;
				}
			}
		}
		if(leftVal >= rightVal) {
			return pair;
		}
		if(leftVal + rightVal == target) {
			pair[0] = leftVal;
			pair[1] = rightVal;
			return pair;
		} else if(leftVal + rightVal > target) {
			searchRight = true;
		} else {
			searchLeft = true;
		}
	}
}

 

Reference:

http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

http://www.geeksforgeeks.org/find-if-there-is-a-triplet-in-bst-that-adds-to-0/