Path from the root node to a given node in an N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long ll ; void PrintPathNodes ( ll N ) { vector < ll > arr ; arr . push_back ( 1 ) ; ll k = 1 ; bool flag = true ; while ( k < N ) { if ( flag == true ) { k *= 2 ; flag = false ; } else { k *= 4 ; flag = true ; } if ( k > N ) { break ; } arr . push_back ( k ) ; } ll len = arr . size ( ) ; vector < ll > prefix ( len ) ; prefix [ 0 ] = 1 ; for ( ll i = 1 ; i < len ; ++ i ) { prefix [ i ] = arr [ i ] + prefix [ i - 1 ] ; } vector < ll > :: iterator it = lower_bound ( prefix . begin ( ) , prefix . end ( ) , N ) ; ll ind = it - prefix . begin ( ) ; ll temp = N ; vector < int > path ; path . push_back ( N ) ; while ( ind > 1 ) { ll val = temp - prefix [ ind - 1 ] ; if ( ind % 2 != 0 ) { temp = prefix [ ind - 2 ] + ( val + 1 ) / 2 ; } else { temp = prefix [ ind - 2 ] + ( val + 3 ) / 4 ; } -- ind ; path . push_back ( temp ) ; } if ( N != 1 ) path . push_back ( 1 ) ; for ( int i = path . size ( ) - 1 ; i >= 0 ; i -- ) { cout << path [ i ] << " ▁ " ; } } int main ( ) { ll N = 14 ; PrintPathNodes ( N ) ; return 0 ; }