508. Pair Sum in Search Tree
A shop stores the prices of its products in a binary search tree: keys in a node's left subtree are smaller, keys in its right subtree are larger, and all prices are distinct. A customer wants to buy exactly two different products and spend exactly k in total.
Given root and the integer k, return true if there are two different nodes whose keys add up to k, and false otherwise. A node cannot be paired with itself, and an empty tree or a tree with one node never has such a pair.
Example 1
- Input:
- root = [9,4,14,2,6,11,20], k = 17
- Output:
- true
- Explanation:
The keys 6 and 11 are two different nodes and add up to 17.
Example 2
- Input:
- root = [9,4,14,2,6,11,20], k = 30
- Output:
- false
- Explanation:
No pair of different keys sums to exactly 30; for example 9 + 20 = 29 and 11 + 20 = 31.
Constraints
0 ≤ number of nodes ≤ 104
-109 ≤ Node.val ≤ 109
-2 * 109 ≤ k ≤ 2 * 109, and k fits in a 32-bit signed integer.
The tree is a valid binary search tree with distinct keys. Sums of two keys may need 64-bit arithmetic.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)