package tree;

import java.util.HashSet;

/**
 * Created by gouthamvidyapradhan on 16/12/2017.
 * Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that
 * their sum is equal to the given target.

 Example 1:
 Input:
 5
 / \
 3   6
 / \   \
 2   4   7

 Target = 9

 Output: True
 Example 2:
 Input:
 5
 / \
 3   6
 / \   \
 2   4   7

 Target = 28

 Output: False
 */
public class TwoSumIV {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
    }

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

    private boolean inorder(TreeNode node, HashSet<Integer> set, int k){
        if(node != null){
            int req = k - (node.val);
            if(set.contains(req)){
                return true;
            }
            set.add(node.val);
            if(inorder(node.left, set, k)){
                return true;
            } else{
                if(inorder(node.right, set, k)){
                    return true;
                }
            }
        } return false;
    }
}