News Leaflets
0 11

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.

Structure of the tree

Input: 1 N 2 3 N 4 5 6 N N N N
Output: 0
Explanation: No duplicate subtree found.

Structure of the tree

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++

 ` `  `#include ` `using` `namespace` `std;` ` `  `class` `Node {` `public``:` `    ``int` `data;` `    ``vector children;` `    ``Node(``int` `val) { data = val; }` `};` ` `  `string dfs(Node* root, unordered_map& f)` `{` `    ` `    ``if` `(root == 0)` `        ``return` `""``;` `    ``string s = ``"("``;` `    ``s += to_string(root->data);` `    ` `    ``for` `(``auto` `child : root->children) {` `        ``s += dfs(child, f);` `    ``}` `    ``s += ``')'``;` `    ``f[s]++;` ` `  `    ` `    ``return` `s;` `}` ` `  `int` `duplicateSubtreeNaryTree(Node* root)` `{` `    ` `    ``unordered_map f;` ` `  `    ` `    ``dfs(root, f);` `    ``int` `ans = 0;` ` `  `    ` `    ``for` `(``auto` `p : f)` `        ``if` `(p.second > 1)` `            ``ans++;` ` `  `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` `    ` `    ``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));` ` `  `    ` `    ``cout << duplicateSubtreeNaryTree(root);` ` `  `    ``return` `0;` `}`

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: