Wednesday, 27 Oct 2021

# Queries to calculate sum of the path from root to a given node in given Binary Tree

Queries to calculate sum of the path from root to a given node in given Binary Tree
Given an infinite complete binary tree rooted at node 1, where every ith node has two children, with values 2 * i and 2 * (i + 1). Given another array arr[] consisting of N positive integers, the task for each array element arr[i] is to find the sum of the node values that occur in a path from the root node to the node arr[i].
Examples:

Input: arr[] = {3, 10}Output: 4 18Explanation:Node 3: The path is 3 -> 1. Therefore, the sum of the path is 4.Node 10: The path is 10 -> 5 -> 2 -> 1. Therefore, the sum of node is 18.
Input: arr[] = {1, 4, 20}Output: 1 7 38Explanation:Node 1: The path is 1. Therefore, the sum of the path is 1.Node 4: The path is 4 -> 2 -> 1. Therefore, the sum of node is 7.Node 20: The path is 20 -> 10 -> 5 -> 2 -> 1. Therefore, the sum of node is 38.

Naive Approach: The simplest approach is to perform DFS Traversal for each array element arr[i] to find its path from the current node to the root and print the sum of the node values in that path.Time Complexity: O(N * H), where H is the maximum height of the tree.Auxiliary Space: O(H)
Efficient Approach: The above approach can also be optimized based on the observation that the parent of the node with value N contains the value N/2. Follow the steps below to solve the problem:Initialize a variable, say sumOfNode, to store the sum of nodes in a path.
Traverse the array arr[i] and perform the following steps:
For each element arr[i], update the value of sumOfNode as sumOfNode + X and update arr[i] as arr[i] / 2.
Repeat the above steps while arr[i] is greater than 0.
Print the value of sumOfNode as the result for each array element arr[i].

Below is the implementation of the above approach:

C++

#include
#include
using namespace std;

void sumOfNodeInAPath(int node_value)
{

int sum_of_node = 0;

while (node_value) {

sum_of_node += node_value;

node_value /= 2;
}

cout