A Cartesian tree with sequence S is a binary tree defined by the following two properties:
- It is heap-ordered, so that each parent value is strictly less than that of its children.
- An in-order traversal of the tree produces nodes with values that correspond exactly to S.
Given a sequence S, construct the corresponding Cartesian tree.
Understanding the problem
At first I assumed that the question was asking to construct a cartesian tree from an unsorted list. That is another problem that I plan on writing a separate post about.
The sequence that is provided is already an in-order traversal of the min heap sorted cartesian tree. All we have to do is construct a tree from the in-order sequence
Solving it
We know that the a cartesian tree is one in which the parent is either greater (max heap sorted) or less (min heap sorted) than the child nodes. In this particular problem it is stated that the cartesian tree is min heap sorted.
Therefore we know that the root of the entire tree must be the smallest number. Hence we need to get min of the entire sequence and this is the root.
Because the given sequence is an inorder traversal, we can confidently say that numbers to the left and right of the root will form the left and right children respectively, so we can recursively repeat the same process on the subarrays
