BST Search Path

Difficulty: Easy · Topic: Trees

Build a binary search tree by inserting values left-to-right (ignore duplicates). Then search for target and return the list of node values you visit, starting at the root, until you find target or fall off the tree.

Examples

bst_search_path([5,3,8,2,4,7], 4)
→ [5,3,4]

5 → go left to 3 → go right to 4.

bst_search_path([5,3,8,2,4,7], 8)
→ [5,8]

bst_search_path([5,3,8,2,4,7], 6)
→ [5,8,7]

6 isn't present; the walk ends at 7.

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.