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 i^th 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 18
Explanation:
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 38
Explanation:
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 <iostream> #include <vector> 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 << sum_of_node;        return; }    void findSum(vector<int> Q) {          for (int i = 0; i < Q.size(); i++) {            int node_value = Q[i];            sumOfNodeInAPath(node_value);            cout << " ";     } }    int main() {     vector<int> arr = { 1, 5, 20, 100 };     findSum(arr);        return 0; }

Output:

1 8 38 197

Time Complexity: O(N*log X), where X is the maximum element of the array.
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)