Sum of nodes in the path from root to N | C ++ program for the above approach ; Function to find sum of all nodes from root to N ; If N is equal to 1 ; If N is equal to 2 or 3 ; 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 ; Stores the required sum ; Add temp to the sum ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long ll ; ll sumOfPathNodes ( ll N ) { if ( N == 1 ) { return 1 ; } else if ( N == 2 N == 3 ) { return N + 1 ; } 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 final_ans = 0 ; ll temp = 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 ; final_ans += temp ; } final_ans += ( N + 1 ) ; return final_ans ; } int main ( ) { ll N = 13 ; cout << sumOfPathNodes ( N ) << endl ; return 0 ; }