Problem statement

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

Solution

Preorder is [Root, Left, Right]. So, we can check recursively that for each element there is two groups of elements, one is smaller than root and then greater than root. Potentially it can have $O(n^2)$ time complexity and $O(n)$ space complexity.

There is better algorithm with using explicit stack, where elements always will be in deceasing order. Also we need to keep value for current node ($-\infty$ at start), which we update when we pop elements from stack. We are happy if the order of nodes which we pop from stack will be increasing, so if it is not the case, return False. In the end check that last element of stack is greater than curr.

Complexity

Time complexity is $O(n)$, space is $O(h)$.

Code

class Solution:
    def verifyPreorder(self, preorder):
        stack, curr = [], -float("inf")
        
        for num in preorder:
            while stack and num >= stack[-1]:
                new = stack.pop()
                if new < curr: return False
                curr = new
            stack.append(num)

        return stack[-1] > curr