Path from the root node to a given node in an N | Python3 program for the above approach ; Function to find the path from root to N ; Stores the number of nodes at ( i + 1 ) - th level ; Stores the number of nodes ; Stores if the current level is even or odd ; If level is odd ; If level is even ; If level with node N is reached ; Push into vector ; Compute prefix sums of count of nodes in each level ; Stores the level in which node N s present ; Store path ; Insert temp into path ; Print path ; Driver Code ; Function Call
from bisect import bisect_left NEW_LINE def PrintPathNodes ( N ) : NEW_LINE INDENT arr = [ ] NEW_LINE arr . append ( 1 ) NEW_LINE k = 1 NEW_LINE flag = True NEW_LINE while ( k < N ) : NEW_LINE INDENT if ( flag == True ) : NEW_LINE INDENT k *= 2 NEW_LINE flag = False NEW_LINE DEDENT else : NEW_LINE INDENT k *= 4 NEW_LINE flag = True NEW_LINE DEDENT if ( k > N ) : NEW_LINE INDENT break NEW_LINE DEDENT arr . append ( k ) NEW_LINE DEDENT lenn = len ( arr ) NEW_LINE prefix = [ 0 ] * ( lenn ) NEW_LINE prefix [ 0 ] = 1 NEW_LINE for i in range ( 1 , lenn ) : NEW_LINE INDENT prefix [ i ] = arr [ i ] + prefix [ i - 1 ] NEW_LINE DEDENT it = bisect_left ( prefix , N ) NEW_LINE ind = it NEW_LINE temp = N NEW_LINE path = [ ] NEW_LINE path . append ( N ) NEW_LINE while ( ind > 1 ) : NEW_LINE INDENT val = temp - prefix [ ind - 1 ] NEW_LINE if ( ind % 2 != 0 ) : NEW_LINE INDENT temp = prefix [ ind - 2 ] + ( val + 1 ) // 2 NEW_LINE DEDENT else : NEW_LINE INDENT temp = prefix [ ind - 2 ] + ( val + 3 ) // 4 NEW_LINE DEDENT ind -= 1 NEW_LINE path . append ( temp ) NEW_LINE DEDENT if ( N != 1 ) : NEW_LINE INDENT path . append ( 1 ) NEW_LINE DEDENT for i in range ( len ( path ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT print ( path [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 14 NEW_LINE PrintPathNodes ( N ) NEW_LINE DEDENT