Baseline Binary Search Trees · Concept O(n) · O(1)
A records desk receives a day's transactions already sorted by a walk that always visits smaller amounts before larger ones. Before the batch is filed, a clerk runs one sanity check: a walk with that property must never show an amount that fails to rise against the one before it. One flat scan settles whether the sequence could have come from such a filing tree at all.
Input: An integer array order — a claimed inorder traversal of a binary search tree.
Output: Return true if the sequence is strictly increasing (a valid BST inorder), otherwise false.
1 <= order.length <= 10^5-10^9 <= order[i] <= 10^9Input: {"order":[1,2,3,4]}
Output: true
Every entry rises over its predecessor, so the walk is consistent with a BST.
Input: {"order":[1,3,2]}
Output: false
The 3-to-2 drop breaks the non-decreasing guarantee of any BST inorder.