How To Construct a Cartesian Tree from In-order Traversal

Write an efficient algorithm to construct a Cartesian tree from in-order traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has smaller value than the node itself.

 
For example, following figure shows an example of a Cartesian tree which is derived from the sequence of numbers in inorder order.
 
Cartesian Tree
 
Based on the heap property, the root of the Cartesian tree is the smallest number of the inoder sequence. The idea is to find index of the minimum element in the inoder sequence and construct the root node from it. Now the left subtree consists of the values earlier than the root in the inoder sequence, while the right subtree consists of the values later than the root. We recursively follow this pattern for all nodes in the tree to construct the complete Cartesian tree. This is illustrated below in C++ –

Output:

Inorder Traversal of constructed Cartesian tree is :
9 3 7 1 8 12 10 20 15 18 5


Learn More :