To debug a lookup, you want to see the route a search takes. Given the root of a binary search tree with distinct values and a value val, return the list of values on the path from the root down to the node holding val (both ends included). If val is not stored, return [].
Examples
50
/ \
30 70
/ \ \
20 40 80
\
25
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), val = 25
Output: [50, 30, 20, 25]
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), val = 60
Output: []
Constraints
0 <= number of nodes <= 3000- All values are distinct integers
- O(h) time
Goals
- Record every node visited on a search
- Return an empty path when the value is missing