Do Two Different Stored Values Add Up to a Target
Solve this ProblemYou are given the root of a binary search tree with distinct values and an integer k. Return true if there are two different nodes whose values add up to exactly k, and false otherwise. A node cannot be paired with itself.
A hash set of the values seen so far finds a partner for each node in constant time. Because a search tree is already sorted, a two-pointer scan — one pointer moving up from the smallest value, the other moving down from the largest — does the same job with memory proportional only to the height.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
0 ≤ k ≤ 2000 - ◆
Return true if there are two DIFFERENT nodes whose values add up to exactly k (one node cannot be used twice); otherwise return false
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Remember Every Value Seen and Look for the Partner
GoodVisit the nodes one by one; for each value v, ask whether the partner k − v has already been seen. If so, a pair exists; otherwise remember v and continue. Checking BEFORE remembering guarantees the two values come from different nodes. This works for any binary tree and is O(n) time, but the set of seen values takes O(n) memory (in the worst case all values are stored).
O(n)O(n)1class Solution {
2 public boolean hasPairWithSum(TreeNode root, int k) {
3 return search(root, k, new HashSet<>());
4 }
5
6 private boolean search(TreeNode node, int k, Set<Integer> seen) {
7 if (node == null) return false;
8 if (search(node.left, k, seen)) return true;
9 if (seen.contains(k - node.val)) return true;
10 seen.add(node.val);
11 return search(node.right, k, seen);
12 }
13}Optimal — Two Pointers Walking Inward Using Two Stacks (O(h) Memory)
OptimalOn a sorted list you would use two pointers: one at the smallest value, one at the largest, moving inward depending on whether their sum is too small or too big. A search tree is a sorted list in disguise, so run TWO iterators over it: one that yields values in ascending order (a stack holding the left edge, like a forward inorder walk) and one that yields values in descending order (a stack holding the right edge). Take lo = smallest, hi = largest: if lo + hi equals k, done; if it is smaller, advance lo to the next larger value; if larger, advance hi to the next smaller value; stop when the pointers meet or cross. Each node is produced at most once by each iterator: O(n) time and only O(h) memory for the stacks.
O(n)O(h)1class Solution {
2 public boolean hasPairWithSum(TreeNode root, int k) {
3 Deque<TreeNode> up = new ArrayDeque<>();
4 Deque<TreeNode> down = new ArrayDeque<>();
5 for (TreeNode n = root; n != null; n = n.left) up.push(n);
6 for (TreeNode n = root; n != null; n = n.right) down.push(n);
7 int lo = stepUp(up);
8 int hi = stepDown(down);
9 while (lo < hi) {
10 int sum = lo + hi;
11 if (sum == k) return true;
12 if (sum < k) lo = stepUp(up);
13 else hi = stepDown(down);
14 }
15 return false;
16 }
17
18 private int stepUp(Deque<TreeNode> stack) {
19 if (stack.isEmpty()) return Integer.MAX_VALUE;
20 TreeNode node = stack.pop();
21 for (TreeNode c = node.right; c != null; c = c.left) stack.push(c);
22 return node.val;
23 }
24
25 private int stepDown(Deque<TreeNode> stack) {
26 if (stack.isEmpty()) return -1;
27 TreeNode node = stack.pop();
28 for (TreeNode c = node.left; c != null; c = c.right) stack.push(c);
29 return node.val;
30 }
31}