Given a Binary Tree, the task is to find the most frequent subtree sum that can be obtained by considering every node of the given tree as the root of the subtree. If more than one such sums exist, then print all of them.
Examples:
Input:
5
/ \
2 -4Output: 2 -4 3
Explanation:
The sum of nodes considering 5 as the root of subtree is 5 + 2 – 4 = 3.
The sum of nodes considering 2 as the root of subtree is 2 = 2.
The sum of nodes considering -4 as the root of subtree is -4 = -4.
Since all the sums have same frequency, print all the sum.Input:
4
/ \
2 -4Output: 2
Explanation:
The sum of nodes considering 4 as the root of subtree is 4 + 2 – 4 = 2.
The sum of nodes considering 2 as the root of subtree is 2 = 2.
The sum of nodes considering -4 as the root of subtree is -4 = -4.
Since, sum 2 has maximum frequency ( = 2). Hence, print the value 2.
Approach: The idea to use the DFS Traversal for the given tree to solve the given problem. Follow the below steps to solve the problem:
- Create two auxiliary Hash Map M and F where M is a set of integer keys and corresponding lists, and F will store the frequency of each number.
- Perform the DFS Traversal for the given tree and do the following:
- If the node is NULL, return 0.
- Initialize variables left and right that stores the value of the sum of nodes left and right subtree of the current node.
- Find the sum of currentNode.value + left + right store it in a variable totalSum.
- Now update the frequency of totalSum in the map F.
- Update the frequency of the value F[totalSum] as totalSum in the map M.
- Return the value to totalSum from the current recursive function.
- After the above steps, print all the element of the list M.rbegin().
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the vectorvoid printVector(vector<int> v){ // Traverse vector c for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; }}// TreeNode classclass TreeNode {public: int val; TreeNode *left, *right; // Constructor TreeNode(int data) { val = data; left = NULL; right = NULL; }};// Function to insert node in the// binary treevoid insert(TreeNode** root, int val){ // Initialize Queue queue<TreeNode*> q; // Push the node root q.push(*root); // While Q.size() is there while (q.size()) { // Get the front node TreeNode* temp = q.front(); q.pop(); // If left is NULL if (!temp->left) { if (val) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else { q.push(temp->left); } // If right is NULL if (!temp->right) { if (val) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else { q.push(temp->right); } }}// Function to make the tree from// given node valuesTreeNode* buildTree(vector<int> v){ TreeNode* root = new TreeNode(v[0]); // Traverse and insert node for (int i = 1; i < v.size(); i++) { insert(&root, v[i]); } return root;}// Utility function to find subtree// sum with highest frequency of a// particular nodeint findsubTreeSumUtil( TreeNode* node, map<int, vector<int> >& mpp, map<int, int>& frequency){ if (!node) return 0; // Recur for the left subtree int left = findsubTreeSumUtil( node->left, mpp, frequency); // Recur for the right subtree int right = findsubTreeSumUtil( node->right, mpp, frequency); // Stores sum of nodes of a subtree int totalSum = node->val + left + right; // Update the frequency if (!frequency.count(totalSum)) { mpp[1].push_back(totalSum); frequency[totalSum] = 1; } else { frequency[totalSum]++; mpp[frequency[totalSum]].push_back(totalSum); } // Return the total sum return totalSum;}// Function to find subtree sum with// highest frequency of given treevoid findsubTreeSum(TreeNode* root){ // Store list of nodes attached to // a particular node and frequency // of visited nodes map<int, vector<int> > mpp; map<int, int> frequency; // Base Case if (!root) { printVector({}); return; } // DFS function call findsubTreeSumUtil(root, mpp, frequency); // Print the vector printVector(mpp.rbegin()->second);}// Driver Codeint main(){ // Given nodes of the tree vector<int> v = { 5, 2, -4 }; // Function call to build the tree TreeNode* tree = buildTree(v); // Function Call findsubTreeSum(tree); return 0;} |
Java
// Java program for the above approach// Importing required classesimport java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.LinkedList;import java.util.Queue;import java.util.TreeMap;public class GFG { // Function to print the list static void printVector(ArrayList<Integer> v) { // Traverse list for (int i = 0; i < v.size(); i++) { System.out.print(v.get(i) + " "); } } // TreeNode class static class TreeNode { int val; TreeNode left, right; // Constructor TreeNode(int data) { val = data; left = null; right = null; } } // Function to insert node in the // binary tree static void insert(TreeNode root, int val) { // Initialize Queue Queue<TreeNode> q = new LinkedList<TreeNode>(); // Push the node root q.add(root); // While queue is not empty while (q.isEmpty() == false) { // Get the front node TreeNode temp = q.peek(); q.poll(); // If left is NULL if (temp.left == null) { temp.left = new TreeNode(val); return; } else { q.add(temp.left); } // If right is NULL if (temp.right == null) { temp.right = new TreeNode(val); return; } else { q.add(temp.right); } } } // Function to make the tree from // given node values static TreeNode buildTree(ArrayList<Integer> v) { TreeNode root = new TreeNode(v.get(0)); // Traverse and insert node for (int i = 1; i < v.size(); i++) { insert(root, v.get(i)); } return root; } // Utility function to find subtree // sum with highest frequency of a // particular node static int findsubTreeSumUtil( TreeNode node, TreeMap<Integer, ArrayList<Integer> > mpp, HashMap<Integer, Integer> frequency) { if (node == null) return 0; // Recur for the left subtree int left = findsubTreeSumUtil(node.left, mpp, frequency); // Recur for the right subtree int right = findsubTreeSumUtil(node.right, mpp, frequency); // Stores sum of nodes of a subtree int totalSum = node.val + left + right; // Update the frequency // If there is no node with sub-tree sum equal to // totalSum It is the first occurrence of totalSum // value if (frequency.get(totalSum) == null) { ArrayList<Integer> temp = mpp.get(1); // If there is no sum which has occurred only // once if (temp == null) temp = new ArrayList<Integer>(); temp.add(totalSum); mpp.put(1, temp); frequency.put(totalSum, 1); } // There is a node with sub-tree sum equal to // totalSum else { frequency.put(totalSum, frequency.get(totalSum) + 1); // Get list of sum values which has // occurrence equal to occurrence of totalSum ArrayList<Integer> temp = mpp.get(frequency.get(totalSum)); // If there is no sum which has occurrence // equal to occurrence of totalSum if (temp == null) temp = new ArrayList<Integer>(); temp.add(totalSum); mpp.put(frequency.get(totalSum), temp); } // Return the total sum return totalSum; } // Function to find subtree sum with // highest frequency of given tree static void findsubTreeSum(TreeNode root) { // Store list of nodes attached to // a particular node and frequency // of visited nodes TreeMap<Integer, ArrayList<Integer> > mpp = new TreeMap<Integer, ArrayList<Integer> >(); HashMap<Integer, Integer> frequency = new HashMap<Integer, Integer>(); // Base Case if (root == null) { return; } // DFS function call findsubTreeSumUtil(root, mpp, frequency); // Print the list of most-frequent subtree sum printVector(mpp.lastEntry().getValue()); } // Driver Code public static void main(String args[]) { // Given nodes of the tree ArrayList<Integer> v = new ArrayList<Integer>(); v.addAll(Arrays.asList(5, 2, -4)); // Function call to build the tree TreeNode tree = buildTree(v); // Function Call findsubTreeSum(tree); }}// This code is contributed by jainlovely450 |
Python3
# TreeNode class to represent a node in a binary treeclass TreeNode: def __init__(self, val): self.val = val # value of the node self.left = None # left child of the node self.right = None # right child of the node# Function to insert a node in the binary treedef insert(root, val): # Initialize a queue with the root node q = [root] # While the queue is not empty while q: # Get the front node in the queue temp = q.pop(0) # If the left child of the node is not None if not temp.left: # Insert the value as the left child of the node if val: temp.left = TreeNode(val) else: temp.left = TreeNode(0) # Return after inserting the node return else: # If the left child is not None, append it to the queue q.append(temp.left) # If the right child of the node is not None if not temp.right: # Insert the value as the right child of the node if val: temp.right = TreeNode(val) else: temp.right = TreeNode(0) # Return after inserting the node return else: # If the right child is not None, append it to the queue q.append(temp.right)# Function to build a binary tree from a list of valuesdef buildTree(v): # Create the root node with the first value in the list root = TreeNode(v[0]) # Insert the rest of the values in the list as nodes in the tree for i in range(1, len(v)): insert(root, v[i]) # Return the root node return root# Helper function to find the sum of each subtree # and store the sum and its frequency in mpp and #frequency dictionariesdef findsubTreeSumUtil(node, mpp, frequency) : # If the node is None, return 0 if not node: return 0 # Calculate the sum of the left subtree left = findsubTreeSumUtil(node.left, mpp, frequency) # Calculate the sum of the right subtree right = findsubTreeSumUtil(node.right, mpp, frequency) # Calculate the sum of the current subtree totalSum = node.val + left + right # If the sum has not been seen before if totalSum not in frequency: # Add the sum to the mpp dictionary mpp[1].append(totalSum) # Set the frequency of the sum to 1 frequency[totalSum] = 1 else: # If the sum has been seen before, increase its frequency by 1 frequency[totalSum] += 1 # Add the sum to the mpp dictionary mpp[frequency[totalSum]].append(totalSum) # Return the sum of the current subtree return totalSum# Function to find the sum of the subtree withdef findsubTreeSum(root): # Store list of nodes attached to # a particular node and frequency # of visited nodes mpp = {1: []} frequency = {} if not root: print([]) return findsubTreeSumUtil(root, mpp, frequency) # Print the list of most-frequent subtree sum print(mpp[max(mpp.keys())])# Driver codev = [5, 2, -4]tree = buildTree(v)findsubTreeSum(tree)# This code is contributed by Potta Lokesh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to print the list static void printVector(List<int> v) { // Traverse list for (int i = 0; i < v.Count; i++) { Console.Write(v[i] + " "); } } // TreeNode class class TreeNode { public int val; public TreeNode left, right; // Constructor public TreeNode(int data) { val = data; left = null; right = null; } } // Function to insert node in the // binary tree static void insert(TreeNode root, int val) { // Initialize Queue Queue<TreeNode> q = new Queue<TreeNode>(); // Push the node root q.Enqueue(root); // While queue is not empty while (q.Count != 0) { // Get the front node TreeNode temp = q.Peek(); q.Dequeue(); // If left is NULL if (temp.left == null) { temp.left = new TreeNode(val); return; } else { q.Enqueue(temp.left); } // If right is NULL if (temp.right == null) { temp.right = new TreeNode(val); return; } else { q.Enqueue(temp.right); } } } // Function to make the tree from // given node values static TreeNode buildTree(List<int> v) { TreeNode root = new TreeNode(v[0]); // Traverse and insert node for (int i = 1; i < v.Count; i++) { insert(root, v[i]); } return root; } // Utility function to find subtree // sum with highest frequency of a // particular node static int findsubTreeSumUtil( TreeNode node, SortedDictionary<int, List<int>> mpp, Dictionary<int, int> frequency) { if (node == null) return 0; // Recur for the left subtree int left = findsubTreeSumUtil(node.left, mpp, frequency); // Recur for the right subtree int right = findsubTreeSumUtil(node.right, mpp, frequency); // Stores sum of nodes of a subtree int totalSum = node.val + left + right; // Update the frequency // If there is no node with sub-tree sum equal to // totalSum It is the first occurrence of totalSum // value if (!frequency.ContainsKey(totalSum)) { // If there is no sum which has occurred only // once List<int> temp = mpp.GetValueOrDefault(1, new List<int>()); temp.Add(totalSum); mpp[1] = temp; frequency[totalSum] = 1; } // There is a node with sub-tree sum equal to // totalSum else { frequency[totalSum] = frequency[totalSum] + 1; // Get list of sum values which has // occurrence equal to occurrence of totalSum List<int> temp = mpp.GetValueOrDefault(frequency[totalSum], new List<int>()); temp.Add(totalSum); mpp[frequency[totalSum]] = temp; } // Return the total sum return totalSum; } // Function to find subtree sum with // highest frequency of given tree static void findsubTreeSum(TreeNode root) { // Store list of nodes attached to // a particular node and frequency // of visited nodes SortedDictionary<int, List<int>> mpp = new SortedDictionary<int, List<int>>(); Dictionary<int, int> frequency = new Dictionary<int, int>(); // Base Case if (root == null) { return; } // DFS function call findsubTreeSumUtil(root, mpp, frequency); // Print the list of most-frequent subtree sum printVector(mpp.Last().Value); } // Driver Code public static void Main(string[] args) { List<int> v = new List<int>(); v.AddRange(new int[] { 5, 2, -4 }); // Function call to build the tree TreeNode tree = buildTree(v); // Function Call findsubTreeSum(tree); }}// This code is contributed by princekumaras |
Javascript
// JavaScript equivalentclass TreeNode { constructor(data) { this.val = data; this.left = null; this.right = null; }}const insert = (root, val) => { const q = []; q.push(root); while (q.length) { const temp = q.shift(); if (!temp.left) { temp.left = new TreeNode(val || 0); return; } else { q.push(temp.left); } if (!temp.right) { temp.right = new TreeNode(val || 0); return; } else { q.push(temp.right); } }};const buildTree = (v) => { const root = new TreeNode(v[0]); for (let i = 1; i < v.length; i++) { insert(root, v[i]); } return root;};const findsubTreeSumUtil = (node, mpp, frequency) => { if (!node) return 0; const left = findsubTreeSumUtil(node.left, mpp, frequency); const right = findsubTreeSumUtil(node.right, mpp, frequency); const totalSum = node.val + left + right; if (!frequency[totalSum]) { if (!mpp[1]) mpp[1] = []; mpp[1].push(totalSum); frequency[totalSum] = 1; } else { frequency[totalSum]++; if (!mpp[frequency[totalSum]]) mpp[frequency[totalSum]] = []; mpp[frequency[totalSum]].push(totalSum); } return totalSum;};const findsubTreeSum = (root) => { const mpp = {}; const frequency = {}; if (!root) return []; findsubTreeSumUtil(root, mpp, frequency); const keys = Object.keys(mpp).sort((a, b) => b - a); return mpp[keys[0]];};const v = [5, 2, -4];const tree = buildTree(v);console.log(findsubTreeSum(tree)); |
Output:
2 -4 3
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!
