Verify Preorder Sequence in Binary Search Tree

Problem Id: 255 Difficulty: Medium Tag: Stack Tag: Tree


Intuition

Let consider the example sequence, [5, 2, 1, 3, 6]. First we would try to recover the tree.

5 is the root value, all nodes less than 5 would be on its left subtree. 2 is less than 5, so it is 5's left node. 1 is less than 2, so it is the left node of 2. 3 is greater than 1, so 3 is not left node of 1. Besides, 3 is greater than 2, so it is not in the left subtree of 2. So 3 is either in the right subtree of 2 or the right subtree of 5. Since 3 is less than 5, so it can only be on right subtree of 2. 6 is greater of 2 and even 5, so it could only be the right node of 5. So we could get a tree like this.

    5
   / \
  2   6
 / \
1   3

Here, we could have a stack to mark the path from root to the current node via left node. And once the number is greater than the top value of the stack, it means we are visiting at least the right subtree of that node. So it is required that all other nodes should be greater than that node. Thus, we got the solution.

Solution


class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        lower = float('-inf')
        for num in preorder:
            if num < lower:
                return False
            while len(stack) > 0 and num > stack[-1]:
                lower = stack.pop()
            stack.append(num)
        return True