Cartesian tree from inorder traversal | Segment Tree | Node of a linked list ; 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
class Node : NEW_LINE INDENT def __init__ ( self , data = None , left = None , right = None ) : NEW_LINE INDENT self . data = data NEW_LINE self . right = right NEW_LINE self . left = left NEW_LINE DEDENT DEDENT maxLen = 30 NEW_LINE segtree = [ 0 ] * ( maxLen * 4 ) NEW_LINE def buildTree ( l , r , i , arr ) : NEW_LINE INDENT global segtree NEW_LINE global maxLen NEW_LINE if ( l == r ) : NEW_LINE INDENT segtree [ i ] = l NEW_LINE return l NEW_LINE DEDENT l1 = buildTree ( l , int ( ( l + r ) / 2 ) , 2 * i + 1 , arr ) NEW_LINE r1 = buildTree ( int ( ( l + r ) / 2 ) + 1 , r , 2 * i + 2 , arr ) NEW_LINE if ( arr [ l1 ] > arr [ r1 ] ) : NEW_LINE INDENT segtree [ i ] = l1 NEW_LINE DEDENT else : NEW_LINE INDENT segtree [ i ] = r1 NEW_LINE DEDENT return segtree [ i ] NEW_LINE DEDENT def rangeMax ( l , r , rl , rr , i , arr ) : NEW_LINE INDENT global segtree NEW_LINE global maxLen NEW_LINE if ( r < rl or l > rr ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( l >= rl and r <= rr ) : NEW_LINE INDENT return segtree [ i ] NEW_LINE DEDENT l1 = rangeMax ( l , int ( ( l + r ) / 2 ) , rl , rr , 2 * i + 1 , arr ) NEW_LINE r1 = rangeMax ( int ( ( l + r ) / 2 ) + 1 , r , rl , rr , 2 * i + 2 , arr ) NEW_LINE if ( l1 == - 1 ) : NEW_LINE INDENT return r1 NEW_LINE DEDENT if ( r1 == - 1 ) : NEW_LINE INDENT return l1 NEW_LINE DEDENT if ( arr [ l1 ] > arr [ r1 ] ) : NEW_LINE INDENT return l1 NEW_LINE DEDENT else : NEW_LINE INDENT return r1 NEW_LINE DEDENT DEDENT def inorder ( curr ) : NEW_LINE INDENT if ( curr == None ) : NEW_LINE INDENT return NEW_LINE DEDENT inorder ( curr . left ) NEW_LINE print ( curr . data , end = " ▁ " ) NEW_LINE inorder ( curr . right ) NEW_LINE DEDENT def createCartesianTree ( l , r , arr , n ) : NEW_LINE INDENT if ( r < l ) : NEW_LINE INDENT return None NEW_LINE DEDENT m = rangeMax ( 0 , n - 1 , l , r , 0 , arr ) NEW_LINE curr = Node ( arr [ m ] ) NEW_LINE curr . left = createCartesianTree ( l , m - 1 , arr , n ) NEW_LINE curr . right = createCartesianTree ( m + 1 , r , arr , n ) NEW_LINE return curr NEW_LINE DEDENT arr = [ 8 , 11 , 21 , 100 , 5 , 70 , 55 ] NEW_LINE n = len ( arr ) NEW_LINE buildTree ( 0 , n - 1 , 0 , arr ) NEW_LINE inorder ( createCartesianTree ( 0 , n - 1 , arr , n ) ) NEW_LINE