Skewed BST — Preorder Simulator

Paste a BST preorder (comma or space separated). The page checks whether the BST could be skewed (every node has at most one child) and visualizes the structure.

Algorithm (O(n))

1. For every index i compute suffix min and suffix max of elements after i.
2. For each element A[i] check: suffixMin[i+1] > A[i] OR suffixMax[i+1] < A[i].
3. If true for all i, then every node has at most one child.

Explanation: in preorder of a BST, nodes that follow root must either all be smaller (left subtree) or all larger (right subtree). For a node to have one child only, all the remaining elements must be on the same side of it.

Complexity

Time: O(n) — one pass to build suffix min/max and one pass to verify. Space: O(n) for suffix arrays.