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


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

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of
Shiv Shankar Singh

It don’t seems like the time complexity as O(n). Can anybody clarify?