Two Sum IV - Input is a BST
Decide whether two different nodes of a binary search tree sum to k, with a DFS that checks each node's partner against a set of values already visited.
Problem Understanding
Two Sum IV - Input is a BST: given the root of a binary search tree and an integer k, return true if there are two different nodes whose values add up to k.
Examples: [5,3,6,2,4,null,7], k 9 → true (4 + 5); k 28 → false.
The Intuition: Two Sum With a Different Loop
Two Sum walks an array with a hash map of what it has seen. Walk the tree instead:
- Visit each node with a DFS.
- Look up its partner
k − valin the set of values visited so far. - Remember the value only after checking, so a node never pairs with itself.
Using the BST order instead, inorder gives sorted values (as in Binary Tree Inorder Traversal) and Two Sum II finishes the job with two pointers.
Interactive Walkthrough
k = 9 · OUTLINED = IN THE SET
EMPTY SET
need
:
answer
:
seen
Empty
Find two different nodes that add up to 9. Keep a set of the values visited so far
Next
Visit 5: its partner would be 9 − 5 = 4
root
k
Legend & Complexity
The node being visited
Nodes whose values are in the set
The pair that adds up to k
Time
O(n)
Space
O(n)
The node being visited is filled, nodes already in the set are outlined, and the set is listed beside the tree. Try Self pair to see why the check comes before the add.
Dry Run Table
Input: [5,3,6,2,4,null,7], k = 9 (preorder: 5, 3, 2, 4, …).
| Node | Need | In set? | Set after |
|---|---|---|---|
| 5 | 4 | no | {5} |
| 3 | 6 | no | {5, 3} |
| 2 | 7 | no | {5, 3, 2} |
| 4 | 5 | yes |
Answer: true (5 + 4 = 9).
The Solution Template
DFS with a set. The C version uses a flag array, since LeetCode bounds the values.
Two Sum IV - Input is a BST Code
1var findTarget = function(root, k) {2 const seen = new Set();3 const dfs = (node) => {4 if (!node) return false;5 if (seen.has(k - node.val)) return true;6 seen.add(node.val);7 return dfs(node.left) || dfs(node.right);8 };9 return dfs(root);10};
Edge Cases & Common Mistakes
- Single node: no pair possible; return false.
- Adding before checking: lets a node pair with itself when
k = 2 × val. - Searching only one subtree: the partner can be anywhere, including an ancestor.
- Negative values: the set handles them; the C flag array offsets indices.
- Early exit: return as soon as a pair is found.
Summary
Traverse the tree; at each node check whether k − val is already in a set, then add val. O(n) time and space; inorder + two pointers is the BST-specific alternative.
More practice: DSA interview questions with answers · patterns cheat sheet