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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <vector> using namespace std; // Data structure to store a Cartesian tree node struct Node { int data; Node *left, *right; }; // Function to create a new Cartesian tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Recursive function to perform inorder traversal of a Cartesian tree void inorderTraversal(Node* root) { if (root == nullptr) return; inorderTraversal(root->left); cout << root->data << ' '; inorderTraversal(root->right); } // Function to find index of the minimum element in inorder[start, end] int minElementIndex(vector<int> const &inorder, int start, int end) { int minIndex = start; for (int i = start + 1; i <= end; i++) { if (inorder[minIndex] > inorder[i]) minIndex = i; } return minIndex; } // Recursive function to construct a Cartesian tree from given // inorder sequence Node* constructTree(vector<int> const &inorder, int start, int end) { // base case if (start > end) return nullptr; // Find index of the minimum element in inorder[start, end] int index = minElementIndex(inorder, start, end); // The minimum element in given range of inorder sequence becomes the root Node *root = newNode(inorder[index]); // recursively construct the left subtree root->left = constructTree(inorder, start, index - 1); // recursively construct the right subtree root->right = constructTree(inorder, index + 1, end); // return current node return root; } // main function int main() { // input sequence of numbers representing the in-order sequence vector<int> inorder = { 9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5 }; // construct the Cartesian tree Node *root = constructTree(inorder, 0, inorder.size() - 1); // print the Cartesian tree cout << "Inorder Traversal of constructed Cartesian tree is:\n"; inorderTraversal(root); return 0; } |

`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. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

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