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 nodestruct Node { char key; Node *left, *right;};// A utility function to create a new nodeNode* 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 morebool 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 codeint 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 nodeclass 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 = Nonesubtrees = 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 approachusing System;using System.Collections.Generic;class GFG{// Structure for a binary tree nodepublic class Node { public char key; public Node left, right;};// A utility function to create a new nodestatic 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 morestatic 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 codepublic 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 nodeclass Node { constructor() { this.key = ''; this.left = null; this.right = null; }};// A utility function to create a new nodefunction 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 morefunction 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 codevar 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
