278. Two Sum IV - Input is a BST

Traverse the tree keeping a set of values seen. For each node, if its complement k - value is already in the set, a pair exists.

Hash the complements

The BST property isn't even needed — a single traversal with a hash set works. For each node, check whether k - node.val has already been seen; if so, return true. Otherwise record node.val and continue.

dfs(node):
    if node is None: return False
    if k - node.val in seen: return True
    seen.add(node.val)
    return dfs(node.left) or dfs(node.right)

Worked example

BST [5,3,6,2,4,null,7], k=9 → 4 and 5 sum to 9 → true.

Complexity

• Time: O(n).
• Space: O(n).

import java.util.HashSet;
import java.util.Set;

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

    private boolean dfs(TreeNode node, int k, Set<Integer> seen) {
        if (node == null) return false;
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left, k, seen) || dfs(node.right, k, seen);
    }
}