Binary Tree: Given a binary tree, check if there is duplicate subtree and return the duplicate subtree

Problem Statement:

You are given a root of a subtree, you need to return all the duplicate subtrees

You need to return the root of each subtree.

2 trees are duplicate, if they have the same structure along with same node values.

Example:

Input:

    /*
     *           10
     *         /    \
     *        12     12
     *       / \    /  \
     *      11 14  11   14
     */

Output:

11 
14 
12 11 14 

Solution Explanation:

We will solve the problem by doing post order traversal of the tree.

Along with post order, we will serialize the subtree.

Serialization is a process of converting tree structure into a string representation.

Example a subtree node 2 having a child 4 and 5 will look like “#,#,4,#,#,5,2”.

Once serialized, we can represent each subtree as a unique string, we can use it as a hash table to keep track of the frequency.

If we find the root node, then return the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_preorder(Node *root)
{
    if (root == nullptr)
        return;

    cout << root->data << " ";
    display_preorder(root->left);
    display_preorder(root->right);
}

void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

string serializeSubtrees(Node* node, unordered_map<string, int>& subtrees, vector<Node*>& duplicates) 
{
    if (!node) 
        return "#"; 
    
    string left = serializeSubtrees(node->left, subtrees, duplicates);
    string right = serializeSubtrees(node->right, subtrees, duplicates);
    
    string s = left + "," + right + "," + to_string(node->data); 
    
    if (subtrees[s] == 1) 
        duplicates.push_back(node);
    subtrees[s]++;

    return s;
}

vector<Node*> solution(Node* root) 
{
    unordered_map<string, int> subtrees;

    vector<Node*> duplicates; 
    
    serializeSubtrees(root, subtrees, duplicates); 

    return duplicates;
}


int main(void)
{
    /*
     *           10
     *         /    \
     *        12     12
     *       / \    /  \
     *      11 14  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(12);
    root->left->left = newNode(11);
    root->left->right = newNode(14);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    vector<Node *> ans = solution(root);

    for (Node *node : ans)
    {
        display_preorder(node);
        cout << endl;
    }

    return 0;
}

Output

11 
14 
12 11 14