Price Window Listing
Easy · tree dfs
A market stall keeps the price of every item it sells in a binary search tree. A shopper has a budget window: they will only look at items that cost between lo and hi, both ends included.
Given the root of the tree and the two numbers lo and hi, return a list of every price in the window, from the most expensive to the cheapest. If no price falls in the window, return an empty list.
In a binary search tree, for every node all prices in its left subtree are smaller and all prices in its right subtree are larger. All prices are distinct.
Examples
Example 1
Input: root = [8, 3, 10, 1, 6, null, 14], lo = 4, hi = 10
Output: [10, 8, 6]
The prices 6, 8 and 10 are inside the window. They are listed from the largest to the smallest.
Example 2
Input: root = [8, 3, 10, 1, 6, null, 14], lo = 11, hi = 13
Output: []
No price lies between 11 and 13.
Example 3
Input: root = [5, 2, 7], lo = 2, hi = 7
Output: [7, 5, 2]
Both ends of the window count, so every price is listed.
Constraints
- The number of nodes is in the range [0, 5000].
- 0 <= Node.val <= 10^6, and all values are distinct.
- The tree is a valid binary search tree.
- 0 <= lo <= hi <= 10^6