Lowest Common Ancestor in a Binary Tree | Set 3 ( Using RMQ ) | Python code to find LCA of given two nodes in a tree ; the graph ; level of each node ; the segment tree ; adding edges to the graph ( tree ) ; assigning level to nodes ; storing the dfs traversal in the array e ; making the array l ; making the array h ; if is already stored ; Range minimum query to return the index of minimum in the subarray L [ qs : qe ] ; out of range ; in the range ; constructs the segment tree ; leaf ; Function to get LCA ; Driver Code ; n = number of nodes in the tree q = number of queries to answer ; 1 / | \ 2 3 4 | \ 5 6 / | \ 8 7 9 ( right of 5 ) / | \ | \ 10 11 12 13 14 | 15
maxn = 100005 NEW_LINE g = [ [ ] for i in range ( maxn ) ] NEW_LINE level = [ 0 ] * maxn NEW_LINE e = [ ] NEW_LINE l = [ ] NEW_LINE h = [ 0 ] * maxn NEW_LINE st = [ 0 ] * ( 5 * maxn ) NEW_LINE def add_edge ( u : int , v : int ) : NEW_LINE INDENT g [ u ] . append ( v ) NEW_LINE g [ v ] . append ( u ) NEW_LINE DEDENT def leveling ( src : int ) : NEW_LINE INDENT for i in range ( len ( g [ src ] ) ) : NEW_LINE INDENT des = g [ src ] [ i ] NEW_LINE if not level [ des ] : NEW_LINE INDENT level [ des ] = level [ src ] + 1 NEW_LINE leveling ( des ) NEW_LINE DEDENT DEDENT DEDENT visited = [ False ] * maxn NEW_LINE def dfs ( src : int ) : NEW_LINE INDENT e . append ( src ) NEW_LINE visited [ src ] = True NEW_LINE for i in range ( len ( g [ src ] ) ) : NEW_LINE INDENT des = g [ src ] [ i ] NEW_LINE if not visited [ des ] : NEW_LINE INDENT dfs ( des ) NEW_LINE e . append ( src ) NEW_LINE DEDENT DEDENT DEDENT def setting_l ( n : int ) : NEW_LINE INDENT for i in range ( len ( e ) ) : NEW_LINE INDENT l . append ( level [ e [ i ] ] ) NEW_LINE DEDENT DEDENT def setting_h ( n : int ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT h [ i ] = - 1 NEW_LINE DEDENT for i in range ( len ( e ) ) : NEW_LINE INDENT if h [ e [ i ] ] == - 1 : NEW_LINE INDENT h [ e [ i ] ] = i NEW_LINE DEDENT DEDENT DEDENT def RMQ ( ss : int , se : int , qs : int , qe : int , i : int ) -> int : NEW_LINE INDENT global st NEW_LINE if ss > se : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if se < qs or qe < ss : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if qs <= ss and se <= qe : NEW_LINE INDENT return st [ i ] NEW_LINE DEDENT mid = ( se + ss ) >> 1 NEW_LINE stt = RMQ ( ss , mid , qs , qe , 2 * i + 1 ) NEW_LINE en = RMQ ( mid + 1 , se , qs , qe , 2 * i + 2 ) NEW_LINE if stt != - 1 and en != - 1 : NEW_LINE INDENT if l [ stt ] < l [ en ] : NEW_LINE INDENT return stt NEW_LINE DEDENT return en NEW_LINE DEDENT elif stt != - 1 : NEW_LINE INDENT return stt NEW_LINE DEDENT elif en != - 1 : NEW_LINE INDENT return en NEW_LINE DEDENT DEDENT def segmentTreeConstruction ( ss : int , se : int , i : int ) : NEW_LINE INDENT if ss > se : NEW_LINE INDENT return NEW_LINE DEDENT if ss == se : NEW_LINE INDENT st [ i ] = ss NEW_LINE return NEW_LINE DEDENT mid = ( ss + se ) >> 1 NEW_LINE segmentTreeConstruction ( ss , mid , 2 * i + 1 ) NEW_LINE segmentTreeConstruction ( mid + 1 , se , 2 * i + 2 ) NEW_LINE if l [ st [ 2 * i + 1 ] ] < l [ st [ 2 * i + 2 ] ] : NEW_LINE INDENT st [ i ] = st [ 2 * i + 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT st [ i ] = st [ 2 * i + 2 ] NEW_LINE DEDENT DEDENT def LCA ( x : int , y : int ) -> int : NEW_LINE INDENT if h [ x ] > h [ y ] : NEW_LINE INDENT x , y = y , x NEW_LINE DEDENT return e [ RMQ ( 0 , len ( l ) - 1 , h [ x ] , h [ y ] , 0 ) ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 15 NEW_LINE q = 5 NEW_LINE add_edge ( 1 , 2 ) NEW_LINE add_edge ( 1 , 3 ) NEW_LINE add_edge ( 1 , 4 ) NEW_LINE add_edge ( 3 , 5 ) NEW_LINE add_edge ( 4 , 6 ) NEW_LINE add_edge ( 5 , 7 ) NEW_LINE add_edge ( 5 , 8 ) NEW_LINE add_edge ( 5 , 9 ) NEW_LINE add_edge ( 7 , 10 ) NEW_LINE add_edge ( 7 , 11 ) NEW_LINE add_edge ( 7 , 12 ) NEW_LINE add_edge ( 9 , 13 ) NEW_LINE add_edge ( 9 , 14 ) NEW_LINE add_edge ( 12 , 15 ) NEW_LINE level [ 1 ] = 1 NEW_LINE leveling ( 1 ) NEW_LINE dfs ( 1 ) NEW_LINE setting_l ( n ) NEW_LINE setting_h ( n ) NEW_LINE segmentTreeConstruction ( 0 , len ( l ) - 1 , 0 ) NEW_LINE print ( LCA ( 10 , 15 ) ) NEW_LINE print ( LCA ( 11 , 14 ) ) NEW_LINE DEDENT