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