// Runtime: 1 ms, faster than 100.00% of Java online submissions for Two Sum IV - Input is a BST.
class Solution {
    TreeNode root;

    public boolean findTarget(TreeNode root, int k) {
        this.root = root;
        return findSum(root, k);
    }

    private boolean findSum(TreeNode current, int target) {
        if (current == null) return false;

        if (find(root, target - current.val, current)) return true;
        if (findSum(current.left, target)) return true;
        if (findSum(current.right, target)) return true;
        return false;
    }

    private boolean find(TreeNode current, int target, TreeNode stopNode) {
        if (current == null) return false;

        if (current != stopNode && current.val == target) return true;
        else if (target < current.val) return find(current.left, target, stopNode);
        else return find(current.right, target, stopNode);
    }
}