Two Sum 4 - Input is Binary Search Tree

Problem

Given a binary search tree 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.

OR

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

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.

Examples

Example 1:

          5
         / \
        3   6
	   / \   \
	  2   4   7

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Explanation: 2 such pairs - [5,4], [2,9]

Example 2:

         10
         / \
        9   20

Input: root = [10, 9, 20], k = 40
Output: false

Solution

Method 1 - Using a Hashset and Dfs

This method works for any tree, so it doesn't take care of features offered by BST.

Code

Java

public boolean findTarget(TreeNode root, int k) {
	return dfs(root, k, new HashSet<>());
}

public boolean dfs(TreeNode root, int k, Set<Integer> set){
	if(root == null) {
		return false;
	}
	if(set.contains(k - root.val)) {
		return true;
	}
	set.add(root.val);
	return dfs(root.left, set, k) || dfs(root.right, set, k);
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Create Sorted Array Using Inorder Traversal and Apply 2 Sum

Code

Java

public boolean findTarget(TreeNode root, int k) {
	List<Integer> nums = new ArrayList<>();
	inorder(root, nums);
	for(int i = 0, j = nums.size()-1; i<j;){
		if(nums.get(i) + nums.get(j) == k) {
			return true;
		}
		if(nums.get(i) + nums.get(j) < k){
			i++;
		}
		else {
			j--;
		}
	}
	return false;
}

public void inorder(TreeNode root, List<Integer> nums){
	if(root == null){
		return;
	}
	inorder(root.left, nums);
	nums.add(root.val);
	inorder(root.right, nums);
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n) storing inorder traversal

Method 3 - Using BST Properties

The idea is to use binary search method. For each node, we check if k - node.val exists in this BST.

Code

Java

public boolean findTarget(TreeNode root, int k) {
	return dfs(root, root,  k);
}

public boolean dfs(TreeNode root,  TreeNode curr, int k){
	if(curr == null) {
		return false;
	}
	return exists(root, curr, k - curr.val) || dfs(root, curr.left, k) || dfs(root, curr.right, k);
}

public boolean exists(TreeNode root, TreeNode cur, int value){
	if(root == null) {
		return false;
	}
	return (root.val == value) && (root != curr) 
		|| (root.val < value) && exists(root.right, curr, value) 
			|| (root.val > value) && exists(root.left, curr, value);
}

Complexity

• ⏰ Time complexity: O(n*h)
• 🧺 Space complexity: O(h), h is the height of the tree, which is logn at best case, and n at worst case.

Method 4 - Using BST Iterator

Algo

Using BST Iterator - .

• Since our Binary Tree is a Binary Search Tree, when we traverse elements in-order, elements are sorted. We have seen that in [#Method 2 - Create Sorted Array Using Inorder Traversal and Apply 2 Sum](#method-2---create-sorted-array-using-inorder-traversal-and-apply-2-sum).
• But why not use [Binary Search Tree BST Inorder Iterator](binary-search-tree-bst-inorder-iterator). Then, we can iterate in-order with O(h) time complexity.
• Since our elements are sorted, we can use Two Pointer to search a pair of (left, right) so that left + right = k, where left point to left element in the BST, right point to right element in the BST.

Code

Java

This is the BSTIterator:

class BSTIterator {
    private Stack<TreeNode> st = new Stack<>();
    private boolean reverse;
    BSTIterator(TreeNode root, boolean reverse) {
        this.reverse = reverse;
        push(root);
    }
    int next() {
        TreeNode top = st.pop();
        push(!reverse ? top.right : top.left);
        return top.val;
    }
    private void push(TreeNode root) {
        while (root != null) {
            st.push(root);
            root = !reverse ? root.left : root.right;
        }
    }
}

Using BST Iterator:

public boolean findTarget(TreeNode root, int k) {
	BSTIterator leftItr = new BSTIterator(root, false);
	BSTIterator rightItr = new BSTIterator(root, true);

	int left = leftItr.next(), right = rightItr.next();
	while (left < right) {
		if (left + right == k) return true;
		if (left + right < k)
			left = leftItr.next();
		else
			right = rightItr.next();
	}
	return false;
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of nodes in the BST.
• 🧺 Space complexity: O(h), where h is the height of the BST. The size of stack is up to O(h).