Cartesian tree from inorder traversal | Segment Tree

Last Updated : 12 Jul, 2025

Given an in-order traversal of a cartesian tree, the task is to build the entire tree from it.

Examples:

Input: arr[] = {1, 5, 3} Output: 1 5 3 5 / \ 1 3 Input: arr[] = {3, 7, 4, 8} Output: 3 7 4 8 8 / 7 / \ 3 4

Approach: We have already seen an algorithm here that takes O(NlogN) time on an average but can get to O(N²) in the worst case.
In this article, we will see how to build the cartesian in worst case running time of O(Nlog(N)). For this, we will use segment-tree to answer range-max queries.

Below will be our recursive algorithm on range {L, R}:

Find the maximum in this range {L, R} using range-max query on the segment-tree. Let's say 'M' is index the maximum in the range.
Pick up 'arr[M]' as the value for current node and create a node with this value.
Solve for range {L, M-1} and {M+1, R}.
Set the node returned by {L, M-1} as the left child of current node and {M+1, R} as the right child.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define maxLen 30 // Node of the BST struct node {  int data;  node* left;  node* right;  node(int data)  {  left = NULL;  right = NULL;  this->data = data;  } }; // Array to store segment tree int segtree[maxLen * 4]; // Function to create segment-tree to answer // range-max query int buildTree(int l, int r, int i, int* arr) {  // Base case  if (l == r) {  segtree[i] = l;  return l;  }  // Maximum index in left range  int l1 = buildTree(l, (l + r) / 2,  2 * i + 1, arr);  // Maximum index in right range  int r1 = buildTree((l + r) / 2 + 1,  r, 2 * i + 2, arr);  // If value at l1 > r1  if (arr[l1] > arr[r1])  segtree[i] = l1;  // Else  else  segtree[i] = r1;  // Returning the maximum in range  return segtree[i]; } // Function to answer range max query int rangeMax(int l, int r, int rl,  int rr, int i, int* arr) {  // Base cases  if (r < rl || l > rr)  return -1;  if (l >= rl and r <= rr)  return segtree[i];  // Maximum in left range  int l1 = rangeMax(l, (l + r) / 2, rl,  rr, 2 * i + 1, arr);  // Maximum in right range  int r1 = rangeMax((l + r) / 2 + 1, r,  rl, rr, 2 * i + 2, arr);  // l1 = -1 means left range  // was out-side required range  if (l1 == -1)  return r1;  if (r1 == -1)  return l1;  // Returning the maximum  // among two ranges  if (arr[l1] > arr[r1])  return l1;  else  return r1; } // Function to print the inorder // traversal of the binary tree void inorder(node* curr) {  // Base case  if (curr == NULL)  return;  // Traversing the left sub-tree  inorder(curr->left);  // Printing current node  cout << curr->data << " ";  // Traversing the right sub-tree  inorder(curr->right); } // Function to build cartesian tree node* createCartesianTree(int l, int r, int* arr, int n) {  // Base case  if (r < l)  return NULL;  // Maximum in the range  int m = rangeMax(0, n - 1, l, r, 0, arr);  // Creating current node  node* curr = new node(arr[m]);  // Creating left sub-tree  curr->left = createCartesianTree(l, m - 1, arr, n);  // Creating right sub-tree  curr->right = createCartesianTree(m + 1, r, arr, n);  // Returning current node  return curr; } // Driver code int main() {  // In-order traversal of cartesian tree  int arr[] = { 8, 11, 21, 100, 5, 70, 55 };  // Size of the array  int n = sizeof(arr) / sizeof(int);  // Building the segment tree  buildTree(0, n - 1, 0, arr);  // Building and printing cartesian tree  inorder(createCartesianTree(0, n - 1, arr, n)); }

Java

// Java implementation of the approach import java.util.*; class GFG { static int maxLen = 30; // Node of the BST static class node {  int data;  node left;  node right;  node(int data)  {  left = null;  right = null;  this.data = data;  } }; // Array to store segment tree static int segtree[] = new int[maxLen * 4]; // Function to create segment-tree to answer // range-max query static int buildTree(int l, int r,   int i, int[] arr) {  // Base case  if (l == r)   {  segtree[i] = l;  return l;  }  // Maximum index in left range  int l1 = buildTree(l, (l + r) / 2,  2 * i + 1, arr);  // Maximum index in right range  int r1 = buildTree((l + r) / 2 + 1,  r, 2 * i + 2, arr);  // If value at l1 > r1  if (arr[l1] > arr[r1])  segtree[i] = l1;  // Else  else  segtree[i] = r1;  // Returning the maximum in range  return segtree[i]; } // Function to answer range max query static int rangeMax(int l, int r, int rl,  int rr, int i, int[] arr) {  // Base cases  if (r < rl || l > rr)  return -1;  if (l >= rl && r <= rr)  return segtree[i];  // Maximum in left range  int l1 = rangeMax(l, (l + r) / 2, rl,  rr, 2 * i + 1, arr);  // Maximum in right range  int r1 = rangeMax((l + r) / 2 + 1, r,  rl, rr, 2 * i + 2, arr);  // l1 = -1 means left range  // was out-side required range  if (l1 == -1)  return r1;  if (r1 == -1)  return l1;  // Returning the maximum  // among two ranges  if (arr[l1] > arr[r1])  return l1;  else  return r1; } // Function to print the inorder // traversal of the binary tree static void inorder(node curr) {  // Base case  if (curr == null)  return;  // Traversing the left sub-tree  inorder(curr.left);  // Printing current node  System.out.print(curr.data + " ");  // Traversing the right sub-tree  inorder(curr.right); } // Function to build cartesian tree static node createCartesianTree(int l, int r,  int[] arr, int n) {  // Base case  if (r < l)  return null;  // Maximum in the range  int m = rangeMax(0, n - 1, l, r, 0, arr);  // Creating current node  node curr = new node(arr[m]);  // Creating left sub-tree  curr.left = createCartesianTree(l, m - 1, arr, n);  // Creating right sub-tree  curr.right = createCartesianTree(m + 1, r, arr, n);  // Returning current node  return curr; } // Driver code public static void main(String args[]) {  // In-order traversal of cartesian tree  int arr[] = { 8, 11, 21, 100, 5, 70, 55 };  // Size of the array  int n = arr.length;  // Building the segment tree  buildTree(0, n - 1, 0, arr);  // Building && printing cartesian tree  inorder(createCartesianTree(0, n - 1, arr, n)); } } // This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach # Node of a linked list  class Node: def __init__(self, data = None, left = None, right = None ): self.data = data self.right = right self.left = left maxLen = 30 # Array to store segment tree segtree = [0]*(maxLen * 4) # Function to create segment-tree to answer # range-max query def buildTree(l , r ,i , arr): global segtree global maxLen # Base case if (l == r) : segtree[i] = l return l # Maximum index in left range l1 = buildTree(l, int((l + r) / 2), 2 * i + 1, arr) # Maximum index in right range r1 = buildTree(int((l + r) / 2) + 1,r, 2 * i + 2, arr) # If value at l1 > r1 if (arr[l1] > arr[r1]): segtree[i] = l1 # Else else: segtree[i] = r1 # Returning the maximum in range return segtree[i] # Function to answer range max query def rangeMax(l, r, rl, rr, i, arr): global segtree global maxLen # Base cases if (r < rl or l > rr): return -1 if (l >= rl and r <= rr): return segtree[i] # Maximum in left range l1 = rangeMax(l, int((l + r) / 2), rl, rr, 2 * i + 1, arr) # Maximum in right range r1 = rangeMax(int((l + r) / 2) + 1, r, rl, rr, 2 * i + 2, arr) # l1 = -1 means left range # was out-side required range if (l1 == -1): return r1 if (r1 == -1): return l1 # Returning the maximum # among two ranges if (arr[l1] > arr[r1]): return l1 else: return r1 # Function to print the inorder # traversal of the binary tree def inorder(curr): # Base case if (curr == None): return # Traversing the left sub-tree inorder(curr.left) # Printing current node print(curr.data, end= " ") # Traversing the right sub-tree inorder(curr.right) # Function to build cartesian tree def createCartesianTree(l , r , arr, n): # Base case if (r < l): return None # Maximum in the range m = rangeMax(0, n - 1, l, r, 0, arr) # Creating current node curr = Node(arr[m]) # Creating left sub-tree curr.left = createCartesianTree(l, m - 1, arr, n) # Creating right sub-tree curr.right = createCartesianTree(m + 1, r, arr, n) # Returning current node return curr # Driver code # In-order traversal of cartesian tree arr = [ 8, 11, 21, 100, 5, 70, 55 ] # Size of the array n = len(arr) # Building the segment tree buildTree(0, n - 1, 0, arr) # Building && printing cartesian tree inorder(createCartesianTree(0, n - 1, arr, n)) # This code is contributed by Arnab Kundu

// C# implementation of the approach using System; class GFG  {   static int maxLen = 30;     // Node of the BST   public class node   {   public int data;   public node left;   public node right;   public node(int data)   {   left = null;   right = null;   this.data = data;   }   };     // Array to store segment tree   static int []segtree = new int[maxLen * 4];     // Function to create segment-tree to answer   // range-max query   static int buildTree(int l, int r,   int i, int[] arr)   {   // Base case   if (l == r)   {   segtree[i] = l;   return l;   }     // Maximum index in left range   int l1 = buildTree(l, (l + r) / 2,   2 * i + 1, arr);     // Maximum index in right range   int r1 = buildTree((l + r) / 2 + 1,   r, 2 * i + 2, arr);     // If value at l1 > r1   if (arr[l1] > arr[r1])   segtree[i] = l1;     // Else   else  segtree[i] = r1;     // Returning the maximum in range   return segtree[i];   }     // Function to answer range max query   static int rangeMax(int l, int r, int rl,   int rr, int i, int[] arr)   {     // Base cases   if (r < rl || l > rr)   return -1;   if (l >= rl && r <= rr)   return segtree[i];     // Maximum in left range   int l1 = rangeMax(l, (l + r) / 2, rl,   rr, 2 * i + 1, arr);     // Maximum in right range   int r1 = rangeMax((l + r) / 2 + 1, r,   rl, rr, 2 * i + 2, arr);     // l1 = -1 means left range   // was out-side required range   if (l1 == -1)   return r1;   if (r1 == -1)   return l1;     // Returning the maximum   // among two ranges   if (arr[l1] > arr[r1])   return l1;   else  return r1;   }     // Function to print the inorder   // traversal of the binary tree   static void inorder(node curr)   {     // Base case   if (curr == null)   return;     // Traversing the left sub-tree   inorder(curr.left);     // Printing current node   Console.Write(curr.data + " ");     // Traversing the right sub-tree   inorder(curr.right);   }     // Function to build cartesian tree   static node createCartesianTree(int l, int r,   int[] arr, int n)   {   // Base case   if (r < l)   return null;     // Maximum in the range   int m = rangeMax(0, n - 1, l, r, 0, arr);     // Creating current node   node curr = new node(arr[m]);     // Creating left sub-tree   curr.left = createCartesianTree(l, m - 1,  arr, n);     // Creating right sub-tree   curr.right = createCartesianTree(m + 1, r,   arr, n);     // Returning current node   return curr;   }     // Driver code   public static void Main()   {   // In-order traversal of cartesian tree   int []arr = { 8, 11, 21, 100, 5, 70, 55 };     // Size of the array   int n = arr.Length;     // Building the segment tree   buildTree(0, n - 1, 0, arr);     // Building && printing cartesian tree   inorder(createCartesianTree(0, n - 1, arr, n));   }  } // This code is contributed by AnkitRai01

JavaScript

<script> // Javascript implementation of the approach var maxLen = 30;  // Node of the BST  class node  {   constructor(data)  {  this.data = data;  this.left = null;  this.right = null;  } };  // Array to store segment tree  var segtree = Array(maxLen * 4).fill(0); // Function to create segment-tree to answer  // range-max query  function buildTree(l, r, i, arr)  {     // Base case   if (l == r)   {   segtree[i] = l;   return l;   }   // Maximum index in left range   var l1 = buildTree(l, parseInt((l + r) / 2),   2 * i + 1, arr);   // Maximum index in right range   var r1 = buildTree(parseInt((l + r) / 2) + 1,   r, 2 * i + 2, arr);   // If value at l1 > r1   if (arr[l1] > arr[r1])   segtree[i] = l1;   // Else   else  segtree[i] = r1;   // Returning the maximum in range   return segtree[i];  }  // Function to answer range max query  function rangeMax(l, r, rl, rr, i, arr)  {     // Base cases   if (r < rl || l > rr)   return -1;   if (l >= rl && r <= rr)   return segtree[i];   // Maximum in left range   var l1 = rangeMax(l, parseInt((l + r) / 2), rl,   rr, 2 * i + 1, arr);   // Maximum in right range   var r1 = rangeMax(parseInt((l + r) / 2) + 1, r,   rl, rr, 2 * i + 2, arr);   // l1 = -1 means left range   // was out-side required range   if (l1 == -1)   return r1;   if (r1 == -1)   return l1;   // Returning the maximum   // among two ranges   if (arr[l1] > arr[r1])   return l1;   else  return r1;  }  // Function to print the inorder  // traversal of the binary tree  function inorder(curr)  {     // Base case   if (curr == null)   return;   // Traversing the left sub-tree   inorder(curr.left);   // Printing current node   document.write(curr.data + " ");   // Traversing the right sub-tree   inorder(curr.right);  }  // Function to build cartesian tree  function createCartesianTree(l, r, arr, n)  {     // Base case   if (r < l)   return null;   // Maximum in the range   var m = rangeMax(0, n - 1, l, r, 0, arr);   // Creating current node   var curr = new node(arr[m]);   // Creating left sub-tree   curr.left = createCartesianTree(l, m - 1,  arr, n);   // Creating right sub-tree   curr.right = createCartesianTree(m + 1, r,   arr, n);   // Returning current node   return curr;  }  // Driver code  // In-order traversal of cartesian tree  var arr = [ 8, 11, 21, 100, 5, 70, 55 ]; // Size of the array  var n = arr.length;  // Building the segment tree  buildTree(0, n - 1, 0, arr);  // Building && printing cartesian tree  inorder(createCartesianTree(0, n - 1, arr, n));  // This code is contributed by noob2000 </script>

Output:

8 11 21 100 5 70 55

Time complexity: O(N+logN)
Auxiliary Space: O(N).

Cartesian tree from inorder traversal | Segment Tree

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

My Profile

Thank You!

What kind of Experience do you want to share?