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++ –

 

Download   Run Code

Output:

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

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of