445. Two Sum IV - Input is a BST
You are given the root of a binary search tree and an integer k. Your function receives the root node and k, and returns true if there exist two different nodes in the tree whose values sum to exactly k, and false otherwise.
A node may not be paired with itself: if k = 8 and the tree contains a single 4, that is not a match (but two distinct nodes holding 4 would be — this tree's values happen to be distinct, so that never arises).
Can you make the sorted structure of the BST do some work for you?
Example 1:
Input: root = [5, 3, 6, 2, 4, null, 7], k = 9
Output: true
Explanation: Several pairs work here: 2 + 7 = 9, 3 + 6 = 9, and 5 + 4 = 9. One is enough.
Example 2:
Input: root = [5, 3, 6, 2, 4, null, 7], k = 28
Output: false
Explanation: The two largest values are 6 and 7, so no pair can reach 28.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁴ ≤ Node.val ≤ 10⁴
- The tree is a valid binary search tree with distinct values.
- -10⁵ ≤ k ≤ 10⁵
Hints:
Forget the BST for a moment — this is plain Two Sum over a collection you happen to visit by traversal. While walking the tree, what structure answers "have I already seen k − value?" in O(1)?
To actually exploit the BST: an inorder traversal emits the values in ascending order. On a sorted sequence, aim two pointers at the ends and walk inward — a sum that is too small advances the left pointer, too large retreats the right one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 3, 6, 2, 4, null, 7], k = 9
Expected output: true