Two Sum IV - Input is a BST

Problem

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise. (link)

Example 1:

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

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 10<sup>4</sup>].

• -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>

• root is guaranteed to be a valid binary search tree.

• -10<sup>5</sup> <= k <= 10<sup>5</sup>

Solution

Brute Force Approach

This is similar to the 2-sum problem, where we store all the elements in a set and check if the complementary element is present.

Time - O(n)

Space - O(n)

class Solution {

    private boolean find(TreeNode root, int k, Set<Integer> set){
        if(root == null){
            return false;
        }

        int counterNo = k - root.val;
        if(set.contains(counterNo)){
            return true;
        }
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    } 
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return find(root,k,set);
    }
}

Optimal Approach

We will use two pointers, one on the left and one on the right. Each pointer will perform an inorder traversal of the binary tree. Since an inorder traversal of a binary tree gives us a list in sorted ascending order, we can use the concept of a Binary Search Iterator to get the next element and the previous element. One BSTIterator will be for the left pointer and another for the right pointer. Iterating backward is the reverse of inorder traversal, which means moving completely to the right, then to the parent's left, and then completely to the right again.

Time - O(n)

Space - O(H) x 2

class BSTIterator{
    Deque<TreeNode> stack = new ArrayDeque<>();
    boolean reverse = false;

    public BSTIterator(TreeNode root){
        pushAllLeft(root);
    }

    public BSTIterator(TreeNode root, boolean reverse){
        pushAllRight(root);
        this.reverse = reverse;
    }

    public int next(){
        TreeNode node = stack.pop();

        if(reverse){
            pushAllRight(node.left);
        }
        else{
            pushAllLeft(node.right);
        }

        return node.val;
    }

    private void pushAllLeft(TreeNode node){
        while(node!=null){
            stack.push(node);
            node = node.left;
        }
    }

    private void pushAllRight(TreeNode node){
        while(node!=null){
            stack.push(node);
            node = node.right;
        }
    }

}
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        BSTIterator leftIterator = new BSTIterator(root);
        BSTIterator rightIterator = new BSTIterator(root,true);

        int left = leftIterator.next();
        int right = rightIterator.next();
        while(left<right){
            int sum = left+right;
            if(sum == k) return true;

            if(sum < k){
                left = leftIterator.next();
            }
            else{
                right = rightIterator.next();
            }
        }
        return false;
    }
}