Two Sum IV — Input is BST
Two Sum IV — Input is BST: do two nodes in the BST sum to k?
- The number of nodes in the tree is in the range [1, 10⁴].
- -10⁴ <= Node.val <= 10⁴
- root is guaranteed to be a valid binary search tree.
- -10⁵ <= k <= 10⁵
Intuition
The two sum iv input is bst problem asks whether two different nodes in a binary search tree add up to k. The name is a hint about the structure, but the simplest correct answer barely uses it.
At heart this is Two Sum with a tree instead of an array. Walk the tree in any order keeping a set of values already seen; at each node, check whether k − value is in that set. If it is, the pair exists. The traversal order is irrelevant — every node eventually meets every earlier node through the set.
That is O(n) time and O(n) space and it is a perfectly good answer.
The BST property enables a second approach worth knowing. An inorder traversal emits values in sorted order, and on a sorted sequence two pointers converge from both ends: if the sum is too small advance the left pointer, if too large retreat the right. That is the classic Two Sum II technique.
The trade-off between them is the real content of the question:
- The hash-set version is shortest and needs no ordering.
- The two-pointer version needs the sorted array, so it also costs O(n) space — unless you run two BST iterators in opposite directions, which brings space down to O(h).
That last variant is what an interviewer is usually fishing for when they specify a BST rather than a binary tree.
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
Before reading on: price up what counting everything costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(n) space.
Treat it as Two Sum with a set
Traverse the tree in any order, keeping a set of visited values. At each node, if k - node.val is already in the set, return true; otherwise add the node's value. The BST ordering is not needed at all for this version.
Guard against reusing one node
The two values must come from different nodes. Checking the set before inserting the current value handles this: a node can never pair with itself, since its own value is not yet present when it is tested.
Use inorder for the sorted alternative
An inorder traversal of a BST produces values in ascending order. Collect them into an array, then converge two pointers from the ends — advance the left when the sum is too small, retreat the right when it is too large.
Run two iterators for O(h) space
Instead of materialising the array, drive one BST iterator forward and another backward. This is the only version that beats O(n) space, and it is what makes the BST framing worth mentioning rather than incidental.
Cost of the options
All three are O(n) time. The set and array versions use O(n) space; the two-iterator version uses O(h), which is O(log n) on a balanced tree. Say which trade you are making rather than defaulting silently to the shortest code.
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.