Given a rooted tree having N vertices, an array values[ ], which represents the value assigned to each node, and a vertex V, the task is to calculate the sum of values of nodes and immediate neighbors lying in the path from the root(always 0) to V.
Examples:
Input: N = 8, values = {1, 2, 3, 0, 0, 4, 3, 6}, V = 7
Output: 16
Explanation:
Path from root (0) to V (7) = 0 -> 1 -> 4 -> 7
Neighbors of 0 = (2, 3), Sum = 1(node 0) + 3(node 2) + 0(node 3) = 4
Neighbors of 1 = (5), Sum = 2(node 1) + 4(node 5) = 6
No neighbor of 4, Sum = 0(node 4) = 0
No neighbor of 7, Sum = 6(node 7) = 6
Total sum = 4 + 6 + 0 + 6 = 16Input: N = 5, values = {5, 6, 2, 9, 0}, V = 2
Output: 13
Approach:
The idea is to store the parent of each node in an array and add the value of each parent with its child and store it in the parent node. Now, each node will hold sum of its value and value of corresponding neighbors. Use this array to find the required sum of the path from root to vertex V.
Follow the steps below to solve the problem:
- Initialize an array to store the values of each node and its corresponding neighbors using DFS Traversal.
- Iterate from vertex V to root using the array and keep adding the value of all the nodes found on the path.
- Finally, print the obtained sum.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Creating Adjacency listvector<vector<int>> constructTree(int n, vector<vector<int>> edges) { vector<vector<int>> adjl(n); for (auto e : edges) { int u = e[0]; int v = e[1]; adjl[u].push_back(v); adjl[v].push_back(u); } return adjl;}// Function to perform DFS traversalvoid DFS(vector<vector<int>> adjl, vector<int> &parent, int u, int p) { // Initializing parent of each node to p parent[u] = p; // Iterate over the children for (int v : adjl[u]) { if (v != p) { DFS(adjl, parent, v, u); } }}// Function to add values of children to// respective parent nodesvector<int> valuesFromChildren(vector<int> parent, vector<int> values) { vector<int> valuesChildren(parent.size()); for (int i = 0; i < parent.size(); i++) { // Root node if (parent[i] == -1) continue; else { int p = parent[i]; valuesChildren[p] += values[i]; } } return valuesChildren;}// Function to return sum of values of// each node in path from V to the rootint findSumOfValues(int v, vector<int> parent, vector<int> valuesChildren) { int cur_node = v; int sum = 0; // Path from node V to root node while (cur_node != -1) { sum += valuesChildren[cur_node]; cur_node = parent[cur_node]; } return sum;}// Driver Codeint main() { int n = 8; // Insert edges into the graph vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {4, 7}, {3, 6}}; int v = 7; // Values assigned to each vertex vector<int> values = {1, 2, 3, 0, 0, 4, 3, 6}; // Constructing the tree // using adjacency list vector<vector<int>> adjl = constructTree(n, edges); // Parent array vector<int> parent(n); // store values in the parent array DFS(adjl, parent, 0, -1); // Add values of children to the parent vector<int> valuesChildren = valuesFromChildren(parent, values); // Find sum of nodes lying in the path int sum = findSumOfValues(v, parent, valuesChildren); // Add root node since // its value is not included yet sum += values[0]; cout << sum << endl;}// This code is contributed by// sanjeev2552 |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Creating Adjacency list private static List<List<Integer> > constructTree(int n, int[][] edges) { List<List<Integer> > adjl = new ArrayList<List<Integer> >(); for (int i = 0; i < n; i++) { adjl.add(new ArrayList<Integer>()); } for (int[] e : edges) { int u = e[0]; int v = e[1]; adjl.get(u).add(v); adjl.get(v).add(u); } return adjl; } // Function to perform DFS traversal private static void DFS( List<List<Integer> > adjl, int[] parent, int u, int p) { // Initializing parent of each node to p parent[u] = p; // Iterate over the children for (int v : adjl.get(u)) { if (v != p) { DFS(adjl, parent, v, u); } } } // Function to add values of children to // respective parent nodes private static int[] valuesFromChildren( int[] parent, int[] values) { int[] valuesChildren = new int[parent.length]; for (int i = 0; i < parent.length; i++) { // Root node if (parent[i] == -1) continue; else { int p = parent[i]; valuesChildren[p] += values[i]; } } return valuesChildren; } // Function to return sum of values of // each node in path from V to the root private static int findSumOfValues( int v, int[] parent, int[] valuesChildren) { int cur_node = v; int sum = 0; // Path from node V to root node while (cur_node != -1) { sum += valuesChildren[cur_node]; cur_node = parent[cur_node]; } return sum; } // Driver Code public static void main(String[] args) { int n = 8; // Insert edges into the graph int[][] edges = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 4 }, { 1, 5 }, { 4, 7 }, { 3, 6 } }; int v = 7; // Values assigned to each vertex int[] values = new int[] { 1, 2, 3, 0, 0, 4, 3, 6 }; // Constructing the tree // using adjacency list List<List<Integer> > adjl = constructTree(n, edges); // Parent array int[] parent = new int[n]; // store values in the parent array DFS(adjl, parent, 0, -1); // Add values of children to the parent int[] valuesChildren = valuesFromChildren(parent, values); // Find sum of nodes lying in the path int sum = findSumOfValues( v, parent, valuesChildren); // Add root node since // its value is not included yet sum += values[0]; System.out.println(sum); }} |
Python3
# Python3 program to implement the above approach# Creating Adjacency listdef constructTree(n, edges): adjl = [] for i in range(n): adjl.append([]) for i in range(len(edges)): u = edges[i][0] v = edges[i][1] adjl[u].append(v) adjl[v].append(u) return adjl # Function to perform DFS traversaldef DFS(adjl, parent, u, p): # Initializing parent of each node to p parent[u] = p # Iterate over the children for v in adjl[u]: if (v != p): DFS(adjl, parent, v, u) # Function to add values of children to# respective parent nodesdef valuesFromChildren(parent, values): valuesChildren = [0]*(len(parent)) for i in range(len(parent)): # Root node if (parent[i] == -1): continue else: p = parent[i] valuesChildren[p] += values[i] return valuesChildren # Function to return sum of values of# each node in path from V to the rootdef findSumOfValues(v, parent, valuesChildren): cur_node = v Sum = 0 # Path from node V to root node while (cur_node != -1): Sum += valuesChildren[cur_node] cur_node = parent[cur_node] return Sumn = 8 # Insert edges into the graphedges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 4, 7 ], [ 3, 6 ] ]v = 7# Values assigned to each vertexvalues = [ 1, 2, 3, 0, 0, 4, 3, 6 ]# Constructing the tree# using adjacency listadjl = constructTree(n, edges)# Parent arrayparent = [0]*(n)# store values in the parent arrayDFS(adjl, parent, 0, -1)# Add values of children to the parentvaluesChildren = valuesFromChildren(parent, values)# Find sum of nodes lying in the pathSum = findSumOfValues(v, parent, valuesChildren)# Add root node since# its value is not included yetSum += values[0]print(Sum)# This code is contributed by suresh07. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Creating Adjacency listprivate static List<List<int>> constructTree(int n, int[,] edges){ List<List<int> > adjl = new List<List<int> >(); for(int i = 0; i < n; i++) { adjl.Add(new List<int>()); } for(int i = 0; i < edges.GetLength(0); i++) { int u = edges[i, 0]; int v = edges[i, 1]; adjl[u].Add(v); adjl[v].Add(u); } return adjl;}// Function to perform DFS traversalprivate static void DFS(List<List<int> > adjl, int[] parent, int u, int p){ // Initializing parent of each node to p parent[u] = p; // Iterate over the children foreach(int v in adjl[u]) { if (v != p) { DFS(adjl, parent, v, u); } }}// Function to add values of children to// respective parent nodesprivate static int[] valuesFromChildren(int[] parent, int[] values){ int[] valuesChildren = new int[parent.Length]; for(int i = 0; i < parent.Length; i++) { // Root node if (parent[i] == -1) continue; else { int p = parent[i]; valuesChildren[p] += values[i]; } } return valuesChildren;}// Function to return sum of values of// each node in path from V to the rootprivate static int findSumOfValues(int v, int[] parent, int[] valuesChildren){ int cur_node = v; int sum = 0; // Path from node V to root node while (cur_node != -1) { sum += valuesChildren[cur_node]; cur_node = parent[cur_node]; } return sum;}// Driver Codepublic static void Main(string[] args){ int n = 8; // Insert edges into the graph int[, ] edges = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 4 }, { 1, 5 }, { 4, 7 }, { 3, 6 } }; int v = 7; // Values assigned to each vertex int[] values = new int[] { 1, 2, 3, 0, 0, 4, 3, 6 }; // Constructing the tree // using adjacency list List<List<int>> adjl = constructTree(n, edges); // Parent array int[] parent = new int[n]; // store values in the parent array DFS(adjl, parent, 0, -1); // Add values of children to the parent int[] valuesChildren = valuesFromChildren(parent, values); // Find sum of nodes lying in the path int sum = findSumOfValues(v, parent, valuesChildren); // Add root node since // its value is not included yet sum += values[0]; Console.WriteLine(sum);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program to implement// the above approach// Creating Adjacency listfunction constructTree(n, edges){ let adjl = []; for(let i = 0; i < n; i++) { adjl.push([]); } for(let e = 0; e < edges.length; e++) { let u = edges[e][0]; let v = edges[e][1]; adjl[u].push(v); adjl[v].push(u); } return adjl;}// Function to perform DFS traversalfunction DFS(adjl, parent, u, p){ // Initializing parent of each node to p parent[u] = p; // Iterate over the children for(let v = 0; v < adjl[u].length; v++) { if (adjl[u][v] != p) { DFS(adjl, parent, adjl[u][v], u); } }}// Function to add values of children to// respective parent nodesfunction valuesFromChildren(parent, values){ let valuesChildren = new Array(parent.length); for(let i = 0; i < parent.length; i++) { valuesChildren[i] = 0; } for(let i = 0; i < parent.length; i++) { // Root node if (parent[i] == -1) continue; else { let p = parent[i]; valuesChildren[p] += values[i]; } } return valuesChildren;}// Function to return sum of values of// each node in path from V to the rootfunction findSumOfValues(v, parent, valuesChildren){ let cur_node = v; let sum = 0; // Path from node V to root node while (cur_node != -1) { sum += valuesChildren[cur_node]; cur_node = parent[cur_node]; } return sum;}// Driver Codelet n = 8; // Insert edges into the graphlet edges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 4, 7 ], [ 3, 6 ] ];let v = 7;// Values assigned to each vertexlet values = [ 1, 2, 3, 0, 0, 4, 3, 6 ];// Constructing the tree// using adjacency listlet adjl = constructTree(n, edges);// Parent arraylet parent = new Array(n);for(let i = 0; i < n; i++){ parent[i] = 0;}// Store values in the parent arrayDFS(adjl, parent, 0, -1);// Add values of children to the parentlet valuesChildren = valuesFromChildren( parent, values);// Find sum of nodes lying in the pathlet sum = findSumOfValues( v, parent, valuesChildren);// Add root node since// its value is not included yetsum += values[0];document.write(sum);// This code is contributed by avanitrachhadiya2155</script> |
Output:
16
Time Complexity: O(N)
Auxiliary Space: O(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
