Sum of nodes in the path from root to N-th node in given Tree

0 0 9 minutes read

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>

Output:

Time Complexity: O(log N)
Auxiliary Space: O(log N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!