A backup tool stored a search tree (distinct values) as its preorder sequence (node, then left subtree, then right subtree), but the file might be corrupted. Given the list seq, return True if it is the preorder traversal of some binary search tree with distinct values, otherwise False. The empty list is valid.
Examples
8
/ \
5 10
/ \ \
2 6 12
Input: seq = [8, 5, 2, 6, 10, 12]
Output: True (the preorder of the tree above)
Input: seq = [8, 5, 10, 6]
Output: False (6 comes after 10, so it would sit in 8's right subtree, but 6 < 8)
Constraints
0 <= len(seq) <= 5000- Values are distinct integers
- O(n) time; do not build the tree
Goals
- Characterise preorder sequences of search trees
- Check the sequence in one pass with a stack and a lower bound