This was asked in a 2018 hacker rank interview, not as important as an on-site coding question. However, I see this question as a classic.
— G4G solution based on sorted stack
https://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/ has a tested solution but it’s too cryptic. I added instrumentation to help myself understand it. See my github code.
Insight — at any time, the stack is sorted with the top being the smallest value . If the new item is highest item so far, then stack is wiped clean !
The algo is fairly simple —
- initialize stack with arr i.e. root
- for every new item xx, start looping
- if xx falls below stack top or stack is empty, then push xx, otherwise pop and loop
- so when would we fail. It relies on the “root” variable which holds the top of the stack if non-empty, but frozen (the real tree root) once stack wiped clean !
— My solution 2
My analysis — After we have seen some number of nodes, there’s exactly one possible tree we could construct, so let’s construct it.
Note during the construction, each new node has only one place to go (key insight) and after that we can check if it breaks pre-order.
https://github.com/tiger40490/repo1/blob/py1/py/algo_tree/isPreOrderBST.py is my tested code, probably less elegant than the G4G solution, but I’m still proud of it.
I don’t think any solution (including the G4G) is really O(N). My solution is not inferior. It has a readability advantage. It’s longer but not necessarily slower.