Find Duplicate Subtrees

Difficulty Level Medium
Frequently asked in Amazon Google
TreeViews 2577

Duplicate Subtrees 

Subtrees are said to be duplicate if they have the same node values and structure. Given a binary tree with n nodes. Find all the duplicate subtrees and return their root node.

Find Duplicate Subtrees

Example

Find Duplicate Subtrees

Here, the subtrees 4 and 2->4 appear more than once therefore we will return root nodes of both the subtrees i.e. 4 and 2.

Find Duplicate Subtrees

Here, the subtree 4 appears more than once therefore we will return the root node of the sub-tree i.e. 4.

Using the Hashmap Method

Algorithm for Find Duplicate Subtrees

  1. Initialize a binary tree.
  2. Create an unordered map to store string and int types.
  3. If the node is null return empty string.
  4. Store the values of nodes in a string by converting them to string type.
  5. 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.
  6. Else increment value in the map by 1.
  7. Return string.

Time Complexity: O(n^2) where n is the number of nodes in the binary tree. We visit each node once but the creation may take O(n)O(n) work therefore the time complexity is O(n^2).

Space Complexity: O(n^2) is the space used for hashmap and creation of tree.

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int value; 
    struct Node* left, *right; 
}; 
  
string inorder(Node* node, unordered_map<string, int>& m){ 
    if(!node) 
        return ""; 
  
    string str = "("; 
    str += inorder(node->left, m); 
    str += to_string(node->value); 
    str += inorder(node->right, m); 
    str += ")"; 
  
    if(m[str] == 1) 
        cout << node->value << " "; 
  
    m[str]++; 
  
    return str; 
} 
  
void Duplicates(Node* root){ 
    unordered_map<string, int> m; 
    inorder(root, m); 
} 
  
Node* newNode(int data){ 
    Node* temp = new Node; 
    temp->value = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
int main(){
    
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->right->left = newNode(2); 
    root->right->left->left = newNode(4); 
    root->right->right = newNode(4); 
    Duplicates(root); 
    
    return 0; 
}
4 2

Java Program

import java.util.HashMap; 

class Duplicate_subtress{ 
  
    static HashMap<String, Integer> m; 
    
    static class Node{ 
        int data; 
        Node left; 
        Node right; 
        Node(int data){ 
            this.data = data; 
            left = null; 
            right = null; 
        } 
    } 
    
    static String inorder(Node node){ 
        if(node == null) 
            return ""; 
       
        String str = "("; 
        str += inorder(node.left); 
        str += Integer.toString(node.data); 
        str += inorder(node.right); 
        str += ")"; 
       
        if(m.get(str) != null && m.get(str)==1 ) 
            System.out.print( node.data + " "); 
       
        if(m.containsKey(str)) 
            m.put(str, m.get(str) + 1); 
        else
            m.put(str, 1); 
          
        return str; 
    } 
       
    static void Duplicates(Node root){ 
        m = new HashMap<>(); 
        inorder(root); 
    }  
    
    public static void main(String args[]){
        
        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); 
        Duplicates(root); 
        
    } 
}
4 2

References

Translate »