A customer's gift cards are stored by value in a binary search tree with distinct values. Return True if two different cards add up exactly to total, otherwise False. One card cannot be used twice.
Examples
20
/ \
10 30
/ \ / \
5 15 25 40
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), total = 45
Output: True (20 + 25, or 5 + 40)
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), total = 12
Output: False
Input: root = build_tree([20]), total = 40
Output: False (only one card)
Constraints
0 <= number of nodes <= 3000- All values are distinct integers (possibly negative)
- O(n) time
Goals
- Turn the tree into a sorted sequence
- Search for a pair of distinct entries with a given total