Closest Gift Bundle
Medium · two pointers
A gift shop keeps the prices of its mugs in one binary search tree and the prices of its notebooks in another. In a binary search tree, every price in a node's left subtree is smaller than the node's own price and every price in its right subtree is larger. Inside one tree no price appears twice, but the same price may appear in both trees.
A bundle is one mug plus one notebook, and its cost is the sum of their prices. You have a gift budget in mind and would like a bundle that costs exactly that, or as close to it as possible, above or below.
Return the smallest possible value of |cost - budget| over all bundles (the cost of a bundle minus the budget, without its sign). If some bundle costs exactly the budget, return 0. Both trees contain at least one price.
Examples
Example 1
Input: mugs = [8, 3, 12], notebooks = [20, 10, 30], budget = 35
Output: 2
The bundle 3 + 30 costs 33, which is 2 away from 35. No bundle comes closer.
Example 2
Input: mugs = [5], notebooks = [5], budget = 10
Output: 0
The only bundle costs exactly 10.
Example 3
Input: mugs = [10, 5, 15], notebooks = [7], budget = 4
Output: 8
The cheapest bundle is 5 + 7 = 12, which is 8 above the budget.
Constraints
- The number of nodes in each tree is in the range [1, 1000].
- 1 <= Node.val <= 10^6, and the prices within one tree are distinct.
- Both trees are valid binary search trees.
- 0 <= budget <= 3 * 10^6