0653 - Two Sum IV - Input is a BST

0653 - Two Sum IV - Input is a BST

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.

Examples

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

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

Input: root = [2,1,3], k = 4 Output: true

Input: root = [2,1,3], k = 1 Output: false

Input: root = [2,1,3], k = 3 Output: true

Constraints

The number of nodes in the tree is in the range [1, 104]. -104 <= Node.val <= 104 root is guaranteed to be a valid binary search tree. -105 <= k <= 105

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return helper(root, k, set);
    }
    
    private boolean helper(TreeNode root, int k, Set<Integer> set) {
        if(root == null) return false;
        if(set.contains(root.val)) return true;
        set.add(k - root.val);
        return helper(root.left, k, set) || helper(root.right, k, set);
    }
}