Preorder of a Search Tree

Medium

You are given an array of distinct integers order. Check whether it can be the preorder walk (node first, then its left subtree, then its right subtree) of some binary search tree. In a binary search tree every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. Return True or False. Try to use only O(1) extra memory.

Example 1

order=[10, 4, 2, 7, 15, 12] → True

Root 10; on the left 4 with children 2 and 7; on the right 15 with left child 12. A preorder walk gives exactly this sequence.

Example 2

order=[10, 4, 15, 7] → False

After 15 we are in the right subtree of 10, where every value exceeds 10, so 7 cannot show up.

Example 3

order=[3, 2, 1] → True

Constraints

1 ≤ len(order) ≤ 10⁵
1 ≤ order[i] ≤ 10⁵
All numbers in order are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree Binary Search Tree Recursion Array Binary Tree Monotonic Stack

Similar problems

Search Tree From a Visit Log Medium Peak-Split Tree Medium Pair Across Two Search Trees Medium Search Tree Height From Insertion Order Medium Floor and Ceiling in a Search Tree Medium

Input

order=[10, 4, 2, 7, 15, 12]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.