shreyansh

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

e589704949ee8524fe86e138ada1c291_MD5.webp

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

87b9b31b2658d0e87176e74e1d0bae2b_MD5.jpeg

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);
    }
}