Intuition
Simplest: it's Two Sum on a tree — DFS with a seen-set. Elegant: inorder gives a sorted array, so converge two pointers from both ends. The BST-iterator version runs both pointers directly on the tree in O(h) space.
Once you notice the pair-hunting shape, this is Two Sum with a tree as the input container — the BST ordering is a red herring for the hash-set approach. Any traversal order works, because a hash set doesn't care about sequence. Recognising when a structure's special property is not needed is as useful as recognising when it is.
Approach
Hash-set DFS
Visit every node; if k − val is already seen, done. O(n) time and space, any traversal order.
Sorted two-pointer alternative
Inorder → sorted list; l from the left, r from the right, steer by sum vs k.
Trade-offs
Set version is shortest; two-iterator version wins on space if you already have a BST iterator.
Solution & live demo
Common pitfalls
Adding the node before checking for its complement
seen.add(node.val) if k - node.val in seen: return True
if k - node.val in seen: return True seen.add(node.val)
When k is exactly twice the current value, the node finds itself and reports a pair built from one node used twice. Checking against the values seen earlier guarantees two distinct nodes.
Short-circuiting the recursion incorrectly
dfs(node.left) dfs(node.right) return False
return dfs(node.left) or dfs(node.right)
Discarding the children's return values throws away the answer — a pair found deep in the tree never propagates up, and the function always reports false. Recursive results have to be returned, not just triggered.
Assuming in-order plus two pointers is required
vals = inorder(root) # then two-pointer scan
seen = set() if k - node.val in seen: return True
That's a valid O(n) solution, but it materialises the whole tree first. The hash set answers during the traversal and can stop the moment a pair appears.
Edge cases
Check the set BEFORE inserting the current value — needs a distinct partner.
No pair possible → False.