Cartesian Tree Sort
Cartesian Tree Sort Cartesian tree sort builds a Cartesian tree from the input array, then uses traversal to produce a sorted sequence. A Cartesian tree is a binary tree that satisfies both: heap property on values inorder traversal reproduces the original sequence For sorting, the tree is typically built as a min-heap, so the root holds the smallest element. Problem Given a sequence $A$ of length $n$, reorder it such...