Cartesian tree from inorder traversal | Segment Tree | Javascript 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 ; In - order traversal of cartesian tree ; Size of the array ; Building the segment tree ; Building && printing cartesian tree
var maxLen = 30 ; class node { constructor ( data ) { this . data = data ; this . left = null ; this . right = null ; } } ; var segtree = Array ( maxLen * 4 ) . fill ( 0 ) ; function buildTree ( l , r , i , arr ) { if ( l == r ) { segtree [ i ] = l ; return l ; } var l1 = buildTree ( l , parseInt ( ( l + r ) / 2 ) , 2 * i + 1 , arr ) ; var r1 = buildTree ( parseInt ( ( l + r ) / 2 ) + 1 , r , 2 * i + 2 , arr ) ; if ( arr [ l1 ] > arr [ r1 ] ) segtree [ i ] = l1 ; else segtree [ i ] = r1 ; return segtree [ i ] ; } function rangeMax ( l , r , rl , rr , i , arr ) { if ( r < rl l > rr ) return - 1 ; if ( l >= rl && r <= rr ) return segtree [ i ] ; var l1 = rangeMax ( l , parseInt ( ( l + r ) / 2 ) , rl , rr , 2 * i + 1 , arr ) ; var r1 = rangeMax ( parseInt ( ( 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 ; } function inorder ( curr ) { if ( curr == null ) return ; inorder ( curr . left ) ; document . write ( curr . data + " " ) ; inorder ( curr . right ) ; } function createCartesianTree ( l , r , arr , n ) { if ( r < l ) return null ; var m = rangeMax ( 0 , n - 1 , l , r , 0 , arr ) ; var curr = new node ( arr [ m ] ) ; curr . left = createCartesianTree ( l , m - 1 , arr , n ) ; curr . right = createCartesianTree ( m + 1 , r , arr , n ) ; return curr ; } var arr = [ 8 , 11 , 21 , 100 , 5 , 70 , 55 ] ; var n = arr . length ; buildTree ( 0 , n - 1 , 0 , arr ) ; inorder ( createCartesianTree ( 0 , n - 1 , arr , n ) ) ;