Do Two Different Stored Values Add Up to a Target
Implement hasPairWithSum
You 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.
Example 1:
Input: root = [45,25,65,15,35,55,85,10,null,30,40,null,60], k = 100
Output: true
Example 2:
Input: root = [45,25,65,15,35,55,85,10,null,30,40,null,60], k = 17
Output: false
Example 3:
Input: root = [8], k = 16
Output: false
+ 15 hidden test cases run on Submit.
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
root =
k =