Sunday, January 29, 2023
HomeSoftware DevelopmentDepend of duplicate Subtrees in an N-ary Tree

Depend of duplicate Subtrees in an N-ary Tree


Enhance Article

Save Article

Like Article

Enhance Article

Save Article

Given the foundation of an n-ary tree, the duty is to search out the variety of subtrees which have duplicates within the n-ary tree. Two timber are duplicates if they’ve the identical construction with the identical node values.

Examples:

Enter: 1 N 2 2 3 N 4 N 4 4 3 N N N N N
Output: 2
Clarification: [4], [3] are duplicate subtree.

Structure of the tree

Construction of the tree

Enter: 1 N 2 3 N 4 5 6 N N N N
Output: 0
Clarification: No duplicate subtree discovered.

Structure of the tree

Construction of the tree

Strategy: This downside may be solved utilizing in-order traversal of the Tree.

The concept is to retailer the inorder traversal of each vertex within the type of string and put this string in a map. 

So after inorder traversal of the entire tree we could have all distinct strings in map together with their frequencies. Now we are able to merely iterate over the map and verify if frequency of the string is better than 1, then greater than 1 tree have similar construction. So increment the reply.

Comply with the under steps to implement the thought:

  • To start with, declare an unordered map, and retailer the inorder traversal of the tree in it.
  • For each vertex, retailer the inorder traversal for its subtree within the map.
  • After that, simply verify the frequency of the strings.
    • Whether it is better than 1, then think about it. In any other case not.

Beneath is the implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

class Node {

public:

    int information;

    vector<Node*> youngsters;

    Node(int val) { information = val; }

};

  

string dfs(Node* root, unordered_map<string, int>& f)

{

    

    if (root == 0)

        return "";

    string s = "(";

    s += to_string(root->information);

    

    for (auto little one : root->youngsters) {

        s += dfs(little one, f);

    }

    s += ')';

    f[s]++;

  

    

    return s;

}

  

int duplicateSubtreeNaryTree(Node* root)

{

    

    unordered_map<string, int> f;

  

    

    dfs(root, f);

    int ans = 0;

  

    

    for (auto p : f)

        if (p.second > 1)

            ans++;

  

    

    return ans;

}

  

int principal()

{

    

    Node* root = new Node(1);

    root->youngsters.push_back(new Node(2));

    root->youngsters.push_back(new Node(2));

    root->youngsters.push_back(new Node(3));

    root->youngsters[0]->youngsters.push_back(new Node(4));

    root->youngsters[1]->youngsters.push_back(new Node(4));

    root->youngsters[1]->youngsters.push_back(new Node(4));

    root->youngsters[1]->youngsters.push_back(new Node(3));

  

    

    cout << duplicateSubtreeNaryTree(root);

  

    return 0;

}

Time Complexity: O(V)
Auxiliary Area: O(V2) as a result of we’re storing string for every vertex and the max string size may be V

Associated Articles:

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments