Sum of nodes in the path from root to N | 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
function sumOfPathNodes ( N ) { if ( N == 1 ) { return 1 ; } else if ( N == 2 N == 3 ) { return N + 1 ; } let arr = [ ] ; arr . push ( 1 ) ; let k = 1 ; let flag = true ; while ( k < N ) { if ( flag == true ) { k *= 2 ; flag = false ; } else { k *= 4 ; flag = true ; } if ( k > N ) { break ; } arr . push ( k ) ; } let len = arr . length ; let prefix = new Array ( len ) ; prefix [ 0 ] = 1 ; for ( let i = 1 ; i < len ; ++ i ) { prefix [ i ] = arr [ i ] + prefix [ i - 1 ] ; } let it = lowerBound ( prefix , 0 , len , N ) + 1 ; let ind = it - prefix [ 0 ] ; let final_ans = 0 ; let temp = N ; while ( ind > 1 ) { let val = temp - prefix [ ind - 1 ] ; if ( ind % 2 != 0 ) { temp = prefix [ ind - 2 ] + parseInt ( ( val + 1 ) / 2 , 10 ) ; } else { temp = prefix [ ind - 2 ] + parseInt ( ( val + 3 ) / 4 , 10 ) ; } -- ind ; final_ans += temp ; } final_ans += ( N + 1 ) ; return final_ans ; } function lowerBound ( a , low , high , element ) { while ( low < high ) { let middle = low + parseInt ( ( high - low ) / 2 , 10 ) ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } let N = 13 ; document . write ( sumOfPathNodes ( N ) + " " ) ;