Given the root of an n-ary tree, the task is to find the number of subtrees that have duplicates in the n-ary tree. Two trees are duplicates if they have the same structure with the same node values.
Examples:
Input: 1 N 2 2 3 N 4 N 4 4 3 N N N N N
Output: 2
Explanation: [4], [3] are duplicate subtree.Input: 1 N 2 3 N 4 5 6 N N N N
Output: 0
Explanation: No duplicate subtree found.
Approach: This problem can be solved using in-order traversal of the Tree.
The idea is to store the inorder traversal of every vertex in the form of string and put this string in a map.
So after inorder traversal of the complete tree we will have all distinct strings in map along with their frequencies. Now we can simply iterate over the map and check if frequency of the string is greater than 1, then more than 1 tree have same structure. So increment the answer.
Follow the below steps to implement the idea:
- First of all, declare an unordered map, and store the inorder traversal of the tree in it.
- For every vertex, store the inorder traversal for its subtree in the map.
- After that, just check the frequency of the strings.
- If it is greater than 1, then consider it. Otherwise not.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Structure of a tree node class Node { public : int data; vector<Node*> children; Node( int val) { data = val; } }; // Function to run dfs string dfs(Node* root, unordered_map<string, int >& f) { // Base condition if (root == 0) return "" ; string s = "(" ; s += to_string(root->data); // Dfs call for all children for ( auto child : root->children) { s += dfs(child, f); } s += ')' ; f[s]++; // Return answer string return s; } // Function to count number of duplicate substrings int duplicateSubtreeNaryTree(Node* root) { // Declare a map unordered_map<string, int > f; // DFS call dfs(root, f); int ans = 0; // Loop for traversing the map for ( auto p : f) if (p.second > 1) ans++; // Return the count of duplicate subtrees return ans; } // Driver code int main() { // Building a tree Node* root = new Node(1); root->children.push_back( new Node(2)); root->children.push_back( new Node(2)); root->children.push_back( new Node(3)); root->children[0]->children.push_back( new Node(4)); root->children[1]->children.push_back( new Node(4)); root->children[1]->children.push_back( new Node(4)); root->children[1]->children.push_back( new Node(3)); // Function call cout << duplicateSubtreeNaryTree(root); return 0; } |
Java
import java.util.*; class Node { public int data; public List<Node> children; public Node( int val) { data = val; children = new ArrayList<Node>(); } } public class Main { public static String dfs(Node root, Map<String, Integer> f) { // Base condition if (root == null ) return "" ; String s = "(" + Integer.toString(root.data); // Dfs call for all children for (Node child : root.children) { s += dfs(child, f); } s += ')' ; f.put(s, f.getOrDefault(s, 0 ) + 1 ); return s; } public static int duplicateSubtreeNaryTree(Node root) { Map<String, Integer> f = new HashMap<>(); dfs(root, f); int ans = 0 ; for (Map.Entry<String, Integer> entry : f.entrySet()) { if (entry.getValue() > 1 ) ans++; } return ans; } public static void main(String[] args) { Node root = new Node( 1 ); root.children.add( new Node( 2 )); root.children.add( new Node( 2 )); root.children.add( new Node( 3 )); root.children.get( 0 ).children.add( new Node( 4 )); root.children.get( 1 ).children.add( new Node( 4 )); root.children.get( 1 ).children.add( new Node( 4 )); root.children.get( 1 ).children.add( new Node( 3 )); System.out.println(duplicateSubtreeNaryTree(root)); } } |
Python3
class Node: def __init__( self , val): self .data = val self .children = [] # Function to run dfs def dfs(root, f): # Base condition if root = = None : return "" s = "(" s + = str (root.data) # Dfs call for all children for child in root.children: s + = dfs(child, f) s + = ')' if s in f: f[s] + = 1 else : f[s] = 1 # Return answer string return s # Function to count number of duplicate substrings def duplicateSubtreeNaryTree(root): # Declare a map f = {} # DFS call dfs(root, f) ans = 0 # Loop for traversing the map for p in f: if f[p] > 1 : ans + = 1 # Return the count of duplicate subtrees return ans # Building a tree root = Node( 1 ) root.children.append(Node( 2 )) root.children.append(Node( 2 )) root.children.append(Node( 3 )) root.children[ 0 ].children.append(Node( 4 )) root.children[ 1 ].children.append(Node( 4 )) root.children[ 1 ].children.append(Node( 4 )) root.children[ 1 ].children.append(Node( 3 )) # Function call print (duplicateSubtreeNaryTree(root)) |
C#
// C# code to implement the approach using System; using System.Collections.Generic; using System.Linq; // Structure of a tree node class Node { public int data; public List<Node> children; public Node( int val) { data = val; children = new List<Node>(); } } public class GFG { // Function to run dfs static string dfs(Node root, Dictionary< string , int > f) { // Base condition if (root == null ) return "" ; string s = "(" ; s += root.data.ToString(); // Dfs call for all children foreach ( var child in root.children) { s += dfs(child, f); } s += ')' ; if (f.ContainsKey(s)) f[s]++; else f.Add(s, 1); // Return answer string return s; } // Function to count number of duplicate substrings static int duplicateSubtreeNaryTree(Node root) { // Declare a map Dictionary< string , int > f = new Dictionary< string , int >(); // DFS call dfs(root, f); int ans = 0; // Loop for traversing the map foreach ( var p in f) { if (p.Value > 1) ans++; } // Return the count of duplicate subtrees return ans; } static public void Main() { // Code // Building a tree Node root = new Node(1); root.children.Add( new Node(2)); root.children.Add( new Node(2)); root.children.Add( new Node(3)); root.children[0].children.Add( new Node(4)); root.children[1].children.Add( new Node(4)); root.children[1].children.Add( new Node(4)); root.children[1].children.Add( new Node(3)); // Function call Console.WriteLine(duplicateSubtreeNaryTree(root)); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code for the above approach // Structure of a tree node class Node { constructor(val) { this .data = val; this .children = []; } }; // Function to run dfs function dfs(root, f) { // Base condition if (root == 0) return "" ; let s = "(" ; s += (root.data).toString(); // Dfs call for all children for (let child of root.children) { s += dfs(child, f); } s += ')' ; if (f.has(s)) { f.set(s, f.get(s) + 1) } else { f.set(s, 1); } // Return answer string return s; } // Function to count number of duplicate substrings function duplicateSubtreeNaryTree(root) { // Declare a map let f = new Map(); // DFS call dfs(root, f); let ans = 0; // Loop for traversing the map for (let [key, val] of f) if (val > 1) ans++; // Return the count of duplicate subtrees return ans; } // Driver code // Building a tree let root = new Node(1); root.children.push( new Node(2)); root.children.push( new Node(2)); root.children.push( new Node(3)); root.children[0].children.push( new Node(4)); root.children[1].children.push( new Node(4)); root.children[1].children.push( new Node(4)); root.children[1].children.push( new Node(3)); // Function call console.log(duplicateSubtreeNaryTree(root)); // This code is contributed by Potta Lokesh. |
2
Time Complexity: O(V)
Auxiliary Space: O(V2) because we are storing string for each vertex and the max string length can be V
Related Articles: