Two Sum IV - Input in BST

Problem Statement:

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 falseotherwise.

Example 1: Open: Screenshot 2024-06-12 at 5.09.39 PM.png

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

Example 2:

Open: Screenshot 2024-06-12 at 5.09.57 PM.png

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^4].
• -10^4 <= Node.val <= 10^4
• root is guaranteed to be a valid binary search tree.
• -10^5 <= k <= 10^5

Solution:

1. Two pointers:

class Solution {
    public boolean findTarget(TreeNode root, int target) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
 
        int start = 0;
        int end = res.size() - 1;
 
        while(start < end){
            int sum = res.get(start) + res.get(end);
            if(sum == target){
                return true;
            } else if(sum < target){
                start++;
            } else{
                end--;
            }
        }
        return false;
    }
 
    public void inorder(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

2. HashSet

class Solution {
    public boolean findTarget(TreeNode root, int target) {
        HashSet<Integer> set = new HashSet<>();
        return dfs(root, set, target);
    }
    public boolean dfs(TreeNode root, HashSet<Integer> set, int target){
        if(root == null){
            return false;
        }
 
        if(set.contains(target - root.val)){
            return true;
        }
 
        set.add(root.val);
        return dfs(root.left, set, target) || dfs(root.right, set, target);
    }
}

3. Binary Search