BST lookup path
An embedded datastore keeps its key index as a plain binary search tree with no rebalancing. The list insert_order gives the integer keys in the order they arrived. The first key becomes the root. Every later key starts at the root and walks down, taking the left branch when it is smaller than the key it is standing on and the right branch when it is larger, then hangs off the first empty branch it reaches. A key that is already stored is dropped rather than stored twice. Support engineers want to replay the probes a lookup makes. Return the keys the lookup compares against, from the root downward, in the order it touches them. Include target itself when the lookup lands on it, and stop there. When the lookup runs off the bottom of the tree, still return everything it compared on the way down. Return an empty list when nothing was ever inserted.
index_probe_path(insert_order: list[int], target: int) → list[int][[50,30,70,20,40],40]out[50,30,40][[50,30,70,20,40],60]out[50,70][[10,10,5],5]out[10,5]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[50,30,70,20,40],40][50,30,40]not run yetsample[[50,30,70,20,40],60][50,70]not run yetsample[[10,10,5],5][10,5]not run yetsample