1628. Search Trail
A library catalogue is a binary search tree of distinct integer keys: smaller keys go to the left, larger keys to the right. A lookup starts at the root and, at each node, either stops or moves to one child.
Given the root and an integer target, simulate the lookup and return the keys of the visited nodes in the order they were visited. The lookup stops at the node whose key equals target, which is included in the result. If target is absent, it stops at the last existing node on the way, just before it would step into a missing child; that last node is also included.
The result always contains at least the root's key. Use a simple loop that descends one path. Target complexity: O(h) time, O(h) space for the answer, where h is the tree height.
Example 1
- Input:
- root = [8,3,10,1,6,null,14], target = 6
- Output:
- [8,3,6]
- Explanation:
From 8 go left to 3, then right to 6, where the target is found.
Example 2
- Input:
- root = [8,3,10,1,6,null,14], target = 7
- Output:
- [8,3,6]
- Explanation:
The walk goes 8, 3, 6 and then would step right into a missing child, so it stops at 6.
Example 3
- Input:
- root = [4], target = 4
- Output:
- [4]
- Explanation:
The root holds the target, so the trail is just the root.
Constraints
1 ≤ nodes ≤ 1000
keys are distinct and root is a valid BST
-104 ≤ key, target ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(h)