// Runtime: 2 ms, faster than 95.13% of Java online submissions for Two Sum IV - Input is a BST.
// Memory Usage: 41.9 MB, less than 69.64% of Java online submissions for Two Sum IV - Input is a BST.

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            TreeNode node = q.remove();
            int val = node.val;
            int diff = k - val;
            if (exists(node, root, diff)) {
                return true;
            }
            if (node.left != null) {
                q.add(node.left);
            }
            if (node.right != null) {
                q.add(node.right);
            }
        }

        return false;
    }

    private boolean exists(TreeNode curr, TreeNode node, int val) {
        if(node == null) {
            return false;
        }

        if(node != curr) {
            if(node.val == val) {
                return true;
            }
        }
        if(node.val > val) {
            return exists(curr, node.left, val);
        } else {
            return exists(curr, node.right, val);
        }
    }
}