Duplicate subtree in Binary Tree | SET 2

0 0 6 minutes read

Given a binary tree, the task is to check whether the binary tree contains a duplicate sub-tree of size two or more.

Input:
               A
             /   \ 
           B       C
         /   \       \    
        D     E       B     
                     /  \    
                    D    E
Output: Yes
    B     
  /   \    
 D     E
is the duplicate sub-tree.

Input:
               A
             /   \ 
           B       C
         /   \
        D     E
Output: No

Approach: A DFS based approach has been discussed here. A queue can be used to traverse the tree in a bfs manner. While traversing the nodes, push the node along with its left and right children in a map and if any point the map contains duplicates then the tree contains duplicate sub-trees. For example, if the node is A and its children are B and C then ABC will be pushed to the map. If at any point, ABC has to be pushed again then the tree contains duplicate sub-trees.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure for a binary tree node
struct Node {
    char key;
    Node *left, *right;
};
 
// A utility function to create a new node
Node* newNode(char key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
 
unordered_set<string> subtrees;
 
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
bool dupSubUtil(Node* root)
{
 
    // To store subtrees
    set<string> subtrees;
 
    // Used to traverse tree
    queue<Node*> bfs;
    bfs.push(root);
 
    while (!bfs.empty()) {
        Node* n = bfs.front();
        bfs.pop();
 
        // To store the left and the right
        // children of the current node
        char l = ' ', r = ' ';
 
        // If the node has a left child
        if (n->left != NULL) {
            l = n->left->key;
 
            // Push left node's data
            bfs.push(n->left);
        }
 
        // If the node has a right child
        if (n->right != NULL) {
            r = n->right->key;
 
            // Push right node's data
            bfs.push(n->right);
        }
 
        string subt;
        subt += n->key;
        subt += l;
        subt += r;
 
        if (l != ' ' || r != ' ') {
 
            // If this subtree count is greater than 0
            // that means duplicate exists
            if (!subtrees.insert(subt).second) {
                return true;
            }
        }
    }
    return false;
}
 
// Driver code
int main()
{
    Node* root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('C');
    root->left->left = newNode('D');
    root->left->right = newNode('E');
    root->right->right = newNode('B');
    root->right->right->right = newNode('E');
    root->right->right->left = newNode('D');
 
    cout << (dupSubUtil(root) ? "Yes" : "No");
 
    return 0;
}

Java

import java.util.*;
 
// Structure for a binary tree node
class Node {
    char key;
    Node left, right;
  
    Node(char item) {
        key = item;
        left = right = null;
    }
}
  
class Main {
    static Set<String> subtrees = new HashSet<String>();
  
    // Function that returns true if
    // tree contains a duplicate subtree
    // of size 2 or more
    static boolean dupSubUtil(Node root) {
  
        // To store subtrees
        Set<String> subtrees = new HashSet<String>();
  
        // Used to traverse tree
        Queue<Node> bfs = new LinkedList<Node>();
        bfs.add(root);
  
        while (!bfs.isEmpty()) {
            Node n = bfs.poll();
  
            // To store the left and the right
            // children of the current node
            char l = ' ', r = ' ';
  
            // If the node has a left child
            if (n.left != null) {
                l = n.left.key;
  
                // Push left node's data
                bfs.add(n.left);
            }
  
            // If the node has a right child
            if (n.right != null) {
                r = n.right.key;
  
                // Push right node's data
                bfs.add(n.right);
            }
  
            String subt = "";
            subt += n.key;
            subt += l;
            subt += r;
  
            if (l != ' ' || r != ' ') {
  
                // If this subtree count is greater than 0
                // that means duplicate exists
                if (!subtrees.add(subt)) {
                    return true;
                }
            }
        }
        return false;
    }
  
    // Driver code
    public static void main(String args[]) {
        Node root = new Node('A');
        root.left = new Node('B');
        root.right = new Node('C');
        root.left.left = new Node('D');
        root.left.right = new Node('E');
        root.right.right = new Node('B');
        root.right.right.right = new Node('E');
        root.right.right.left = new Node('D');
  
        System.out.println((dupSubUtil(root) ? "Yes" : "No"));
    }
}

Python3

# Python3 implementation of the approach 
 
# Structure for a binary tree node 
class newNode: 
 
    # Constructor to create a new node 
    def __init__(self, data): 
        self.key = data 
        self.left = None
        self.right = None
 
subtrees = set()
 
# Function that returns true if 
# tree contains a duplicate subtree 
# of size 2 or more 
def dupSubUtil(root):
     
    # To store subtrees 
    subtrees= set()
     
    # Used to traverse tree 
    bfs = []
    bfs.append(root) 
    while (len(bfs)):
        n = bfs[0]
        bfs.pop(0)
         
        # To store the left and the right 
        # children of the current node 
        l = ' '
        r = ' '
         
        # If the node has a left child 
        if (n.left != None):
            x = n.left
            l = x.key
             
            # append left node's data 
            bfs.append(n.left) 
             
        # If the node has a right child 
        if (n.right != None):
            x = n.right
            r = x.key 
             
            # append right node's data 
            bfs.append(n.right) 
             
        subt=""
        subt += n.key 
        subt += l 
        subt += r 
         
        if (l != ' ' or r != ' '):
         
            # If this subtree count is greater than 0 
            # that means duplicate exists 
            subtrees.add(subt)
            if (len(subtrees) > 1):
                return True
                 
    return False
 
# Driver code 
 
root = newNode('A') 
root.left = newNode('B') 
root.right = newNode('C') 
root.left.left = newNode('D') 
root.left.right = newNode('E') 
root.right.right = newNode('B') 
root.right.right.right = newNode('E') 
root.right.right.left = newNode('D') 
 
if dupSubUtil(root):
    print("Yes")
else:
    print("No")
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Structure for a binary tree node
public class Node 
{
    public char key;
    public Node left, right;
};
 
// A utility function to create a new node
static Node newNode(char key)
{
    Node node = new Node();
    node.key = key;
    node.left = node.right = null;
    return node;
}
 
static HashSet<String> subtrees = new HashSet<String>();
 
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
static bool dupSubUtil(Node root)
{
 
    // To store subtrees
    // HashSet<String> subtrees;
 
    // Used to traverse tree
    Queue<Node> bfs = new Queue<Node>();
    bfs.Enqueue(root);
 
    while (bfs.Count != 0)
    {
        Node n = bfs.Peek();
        bfs.Dequeue();
 
        // To store the left and the right
        // children of the current node
        char l = ' ', r = ' ';
 
        // If the node has a left child
        if (n.left != null) 
        {
            l = n.left.key;
 
            // Push left node's data
            bfs.Enqueue(n.left);
        }
 
        // If the node has a right child
        if (n.right != null) 
        {
            r = n.right.key;
 
            // Push right node's data
            bfs.Enqueue(n.right);
        }
 
        String subt = "";
        subt += n.key;
        subt += l;
        subt += r;
 
        if (l != ' ' || r != ' ')
        {
 
            // If this subtree count is greater than 0
            // that means duplicate exists
            if (!subtrees.Contains(subt))
            {
                return true;
            }
        }
    }
    return false;
}
 
// Driver code
public static void Main(String[] args) 
{
    Node root = newNode('A');
    root.left = newNode('B');
    root.right = newNode('C');
    root.left.left = newNode('D');
    root.left.right = newNode('E');
    root.right.right = newNode('B');
    root.right.right.right = newNode('E');
    root.right.right.left = newNode('D');
    if (dupSubUtil(root))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No"); 
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript implementation of the approach
 
// Structure for a binary tree node
class Node 
{
    constructor()
    {
        this.key = '';
        this.left = null;
        this.right = null;
    }
};
 
// A utility function to create a new node
function newNode(key)
{
    var node = new Node();
    node.key = key;
    node.left = node.right = null;
    return node;
}
 
var subtrees = new Set();
 
// Function that returns true if
// tree contains a duplicate subtree
// of size 2 or more
function dupSubUtil(root)
{
 
    // To store subtrees
    // HashSet<String> subtrees;
 
    // Used to traverse tree
    var bfs = [];
    bfs.push(root);
 
    while (bfs.length != 0)
    {
        var n = bfs[0];
        bfs.pop();
 
        // To store the left and the right
        // children of the current node
        var l = ' ', r = ' ';
 
        // If the node has a left child
        if (n.left != null) 
        {
            l = n.left.key;
 
            // Push left node's data
            bfs.push(n.left);
        }
 
        // If the node has a right child
        if (n.right != null) 
        {
            r = n.right.key;
 
            // Push right node's data
            bfs.push(n.right);
        }
 
        var subt = "";
        subt += n.key;
        subt += l;
        subt += r;
 
        if (l != ' ' || r != ' ')
        {
 
            // If this subtree count is greater than 0
            // that means duplicate exists
            if (!subtrees.has(subt))
            {
                return true;
            }
        }
    }
    return false;
}
 
// Driver code
var root = newNode('A');
root.left = newNode('B');
root.right = newNode('C');
root.left.left = newNode('D');
root.left.right = newNode('E');
root.right.right = newNode('B');
root.right.right.right = newNode('E');
root.right.right.left = newNode('D');
if (dupSubUtil(root))
    document.write("Yes");
else
    document.write("No"); 
 
// This code is contributed by rrrtnx.
</script>

Output:

Yes

Time complexity: O(n) where N is no of nodes in a binary tree

Auxiliary Space: O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!