Two Sum in a BST
Easy · tree dfs
You are given the root of a binary search tree (BST) and an integer k. In a BST, every value in a node's left subtree is smaller than the node's own value, every value in its right subtree is larger, and no value appears twice.
Return true if there are two different nodes in the tree whose values add up to k, and false otherwise. A single node cannot be used twice, even if twice its value equals k. An empty tree has no pair.
Examples
Example 1
Input: root = [5, 3, 6, 2, 4, null, 7], k = 9
Output: true
The nodes holding 3 and 6 add up to 9.
Example 2
Input: root = [5, 3, 6, 2, 4, null, 7], k = 28
Output: false
The two largest values are 6 and 7, which add up to only 13.
Example 3
Input: root = [4], k = 8
Output: false
4 + 4 would need the same node twice, and there is no other node.
Constraints
- The number of nodes is in the range [0, 5000], and the height of the tree is at most 1000.
- -10^4 <= Node.val <= 10^4, and all values are distinct.
- The tree is a valid binary search tree.
- -2 * 10^4 <= k <= 2 * 10^4