Sum of nodes in the path from root to N-th node in given Tree
Given an integer N which needs to be present as a value in a node in the last level of a Tree rooted at 1 having nodes numbered from root to the last level by increments of 1. The nodes at every odd level contain 2 children and nodes at every even level contains 4 children. The task is to find the sum of node values in the path from the root to the node N.
Examples:
Input: N = 13
Output: 20
Explanation: The traversal from root 1 to node 13 is 1 -> 2 -> 4 -> 13. Therefore, sum of all nodes in the path = 1 + 2 + 4 + 13 = 20.Input: N = 124
Output: 193
Explanation: The traversal from root 1 to node 124 is 1 -> 2 -> 6 -> 16 -> 44 -> 124. Therefore, sum of all nodes in the path = 1 + 2 + 6 + 16 + 44 + 124 = 193.
Approach: Follow the steps below to solve the problem:
- Initialize an array to store the number of nodes present in each level of the Tree, i.e. {1, 2, 8, 16, 64, 128 ….} and store it.
- Calculate prefix sum of the array i.e. {1 3 11 27 91 219 …….}
- Find the index ind in the prefix sum array which exceeds or is equal to N using lower_bound(). Therefore, ind indicates the number of levels that need to be traversed to reach node N.
- Initialize a variable temp = N and two variables final_ans = 0 and val.
- Decrement ind until it is less than or equal to 1 and keep updating val = temp – prefix[ind – 1].
- Update temp to prefix[ind – 2] + (val + 1) / 2 if ind is odd.
- Otherwise, update prefix[ind – 2] + (val + 3) / 4 if ind is even.
- After completing the above steps, add N + 1 to final_ans and print it as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to find sum of all // nodes from root to N ll sumOfPathNodes(ll N) { // If N is equal to 1 if (N == 1) { return 1; } // If N is equal to 2 or 3 else if (N == 2 || N == 3) { return N + 1; } // Stores the number of // nodes at (i + 1)-th level vector<ll> arr; arr.push_back(1); // Stores the number of nodes ll k = 1; // Stores if the current // level is even or odd bool flag = true ; while (k < N) { // If level is odd if (flag == true ) { k *= 2; flag = false ; } // If level is even else { k *= 4; flag = true ; } // If level with // node N is reached if (k > N) { break ; } // Push into vector arr.push_back(k); } ll len = arr.size(); vector<ll> prefix(len); prefix[0] = 1; // Compute prefix sums of count // of nodes in each level 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); // Stores the level in which // node N s present ll ind = it - prefix.begin(); // Stores the required sum 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; // Add temp to the sum final_ans += temp; } final_ans += (N + 1); return final_ans; } // Driver Code int main() { ll N = 13; // Function Call cout << sumOfPathNodes(N) << endl; return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to find sum of // all nodes from root to N static int sumOfPathNodes( int N) { // If N is equal to 1 if (N == 1 ) { return 1 ; } // If N is equal to // 2 or 3 else if (N == 2 || N == 3 ) { return N + 1 ; } // Stores the number of // nodes at (i + 1)-th level Vector<Integer> arr = new Vector<>(); arr.add( 1 ); // Stores the number // of nodes int k = 1 ; // Stores if the current // level is even or odd boolean flag = true ; while (k < N) { // If level is odd if (flag == true ) { k *= 2 ; flag = false ; } // If level is even else { k *= 4 ; flag = true ; } // If level with // node N is reached if (k > N) { break ; } // Push into vector arr.add(k); } int len = arr.size(); int [] prefix = new int [len]; prefix[ 0 ] = 1 ; // Compute prefix sums of // count of nodes in each // level for ( int i = 1 ; i < len; ++i) { prefix[i] = arr.get(i) + prefix[i - 1 ]; } int it = lowerBound(prefix, 0 , len, N) + 1 ; // Stores the level in which // node N s present int ind = it - prefix[ 0 ]; // Stores the required sum 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; // Add temp to the sum 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; } // Driver Code public static void main(String[] args) { int N = 13 ; // Function Call System.out.print( sumOfPathNodes(N) + "\n" ); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect # Function to find sum of all # nodes from root to N def sumOfPathNodes(N): # If N is equal to 1 if (N = = 1 ): return 1 # If N is equal to 2 or 3 elif (N = = 2 or N = = 3 ): return N + 1 # Stores the number of # nodes at (i + 1)-th level arr = [] arr.append( 1 ) # Stores the number of nodes k = 1 # Stores if the current # level is even or odd flag = True while (k < N): # If level is odd if (flag = = True ): k * = 2 flag = False # If level is even else : k * = 4 flag = True # If level with # node N is reached if (k > N): break # Push into vector arr.append(k) lenn = len (arr) prefix = [ 0 ] * (lenn) prefix[ 0 ] = 1 # Compute prefix sums of count # of nodes in each level for i in range ( 1 , lenn): prefix[i] = arr[i] + prefix[i - 1 ] it = bisect_left(prefix, N) # Stores the level in which # node N s present ind = it # Stores the required sum final_ans = 0 temp = N while (ind > 1 ): 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 - = 1 # Add temp to the sum final_ans + = temp final_ans + = (N + 1 ) return final_ans # Driver Code if __name__ = = '__main__' : N = 13 # Function Call print (sumOfPathNodes(N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function to find sum of // all nodes from root to N static int sumOfPathNodes( int N) { // If N is equal to 1 if (N == 1) { return 1; } // If N is equal to // 2 or 3 else if (N == 2 || N == 3) { return N + 1; } // Stores the number of // nodes at (i + 1)-th level List< int > arr = new List< int >(); arr.Add(1); // Stores the number // of nodes int k = 1; // Stores if the current // level is even or odd bool flag = true ; while (k < N) { // If level is odd if (flag == true ) { k *= 2; flag = false ; } // If level is even else { k *= 4; flag = true ; } // If level with // node N is reached if (k > N) { break ; } // Push into vector arr.Add(k); } int len = arr.Count; int [] prefix = new int [len]; prefix[0] = 1; // Compute prefix sums of // count of nodes in each // level for ( int i = 1; i < len; ++i) { prefix[i] = arr[i] + prefix[i - 1]; } int it = lowerBound(prefix, 0, len, N) + 1; // Stores the level in which // node N s present int ind = it - prefix[0]; // Stores the required sum 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; // Add temp to the sum 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; } // Driver Code public static void Main(String[] args) { int N = 13; // Function Call Console.Write(sumOfPathNodes(N) + "\n" ); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach // Function to find sum of // all nodes from root to N function sumOfPathNodes(N) { // If N is equal to 1 if (N == 1) { return 1; } // If N is equal to // 2 or 3 else if (N == 2 || N == 3) { return N + 1; } // Stores the number of // nodes at (i + 1)-th level let arr = []; arr.push(1); // Stores the number // of nodes let k = 1; // Stores if the current // level is even or odd let flag = true ; while (k < N) { // If level is odd if (flag == true ) { k *= 2; flag = false ; } // If level is even else { k *= 4; flag = true ; } // If level with // node N is reached if (k > N) { break ; } // Push into vector arr.push(k); } let len = arr.length; let prefix = new Array(len); prefix[0] = 1; // Compute prefix sums of // count of nodes in each // level for (let i = 1; i < len; ++i) { prefix[i] = arr[i] + prefix[i - 1]; } let it = lowerBound(prefix, 0, len, N) + 1; // Stores the level in which // node N s present let ind = it - prefix[0]; // Stores the required sum 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; // Add temp to the sum 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; } // Driver code let N = 13; // Function Call document.write(sumOfPathNodes(N) + "</br>" ); // This code is contributed by divyeshrabadiya07 </script> |
20
Time Complexity: O(log N)
Auxiliary Space: O(log N)