Binary Trees: Find Duplicate Subtrees

Problem Statement:

You are given a binary tree, you need to find all the duplicate sub trees.

Example

Input :

       1
      / \
     2   3
    /   / \
   4   2   4
      /
     4

Output :

   2           
  /    and    4
 4

Solution

The solution is very simple, we need to take use of hashing and in-order traversal.

We first do an inorder traversal and store it in a hash table.

Then check if a string value is already present in the map i.e map[string] is equal to one print the value of the node.

Else increment value in the map by 1

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#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 print_dups(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);
    
    print_dups(root);
    return 0;
}

Output:

4 2