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> |
Yes
Time complexity: O(n) where N is no of nodes in a binary tree
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!