Sum of nodes in the path from root to N | Java program for the above approach ; Function to find sum of aint 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
import java . util . * ; class GFG { static int sumOfPathNodes ( int N ) { if ( N == 1 ) { return 1 ; } else if ( N == 2 N == 3 ) { return N + 1 ; } Vector < Integer > arr = new Vector < > ( ) ; arr . add ( 1 ) ; int k = 1 ; boolean flag = true ; while ( k < N ) { if ( flag == true ) { k *= 2 ; flag = false ; } else { k *= 4 ; flag = true ; } if ( k > N ) { break ; } arr . add ( k ) ; } int len = arr . size ( ) ; int [ ] prefix = new int [ len ] ; prefix [ 0 ] = 1 ; for ( int i = 1 ; i < len ; ++ i ) { prefix [ i ] = arr . get ( i ) + prefix [ i - 1 ] ; } int it = lowerBound ( prefix , 0 , len , N ) + 1 ; int ind = it - prefix [ 0 ] ; int final_ans = 0 ; int temp = N ; while ( ind > 1 ) { int 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 ; } static int lowerBound ( int [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } public static void main ( String [ ] args ) { int N = 13 ; System . out . print ( sumOfPathNodes ( N ) + "NEW_LINE"); } }