Binary Trees: Find Duplicate Subtrees

Problem Statement:

You are given a binary tree, you need to get all the duplicate subtree.

You need to return the root of the sub trees.

Example

Output:

The duplicate sub tree are:

   2           
  /    and    4
 4

Here you need to return “2” and “4”

Solution

In the solution we will use map to store the sub trees by doing inorder traversal.

Then during traversing, if we encounter any duplicate subtree then we print them.

Point to be noted is that, simple inorder traversal, will not be sufficient to uniquely identify a tree.

We use ‘(‘ and ‘)’ to represent NULL nodes.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 

using namespace std;


struct node 
{ 
      int data; 
      node *left; 
      node *right; 

    node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
}; 
  
 
string inorder(node* node, unordered_map<string, int>& m)
{
    if (!node)
        return "";
 
    string str = "(";
    str += inorder(node->left, m);
    str += to_string(node->data);
    str += inorder(node->right, m);
    str += ")";
 
    if (m[str] == 1)
        cout << node->data << " ";
 
    m[str]++;
 
    return str;
}
 
void find_duplicate_sub_trees(node* root)
{
    unordered_map<string, int> m;
    inorder(root, m);
}
int main()
{
    node* root = NULL;
    root = new node(1);
    root->left = new node(2);
    root->right = new node(3);
    root->left->left = new node(4);
    root->right->left = new node(2);
    root->right->left->left = new node(4);
    root->right->right = new node(4);

    find_duplicate_sub_trees(root);

    return 0;
}

Output:

4 2