Skip to content

Instantly share code, notes, and snippets.

@SahilKadam
Created March 9, 2017 20:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SahilKadam/fc9c87d7f71d1495ea90c07e2ca3dcf9 to your computer and use it in GitHub Desktop.
Save SahilKadam/fc9c87d7f71d1495ea90c07e2ca3dcf9 to your computer and use it in GitHub Desktop.
Check if a Binary Tree contains duplicate subtrees of size 2 or more
/**
*
* @author Sahil Kadam
*/
import java.util.*;
public class Node{
String name;
Node left,right;
//ArrayList<String> subTree = new ArrayList<String>();
Node(String name){
this.name = name;
this.left = null;
this.right = null;
}
public void setLeft(Node left){
this.left = left;
}
public void setRight(Node right){
this.right = right;
}
public void display(){
System.out.println(name);
}
public String getName(){
return this.name;
}
public static void main(String []args){
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node B1 = new Node("B");
Node D1 = new Node("D");
Node E1 = new Node("E");
Node F = new Node("F");
A.setLeft(B);
A.setRight(C);
B.setLeft(D);
B.setRight(E);
C.setRight(B1);
B1.setLeft(D1);
B1.setRight(E1);
//A.display();
//A.left.left.display();
findDuplicate(A);
}
public static void findDuplicate(Node root){
HashSet subTreeList = getSubTree(root);
if(subTreeList.contains("Duplicate"))
System.out.println("Yes");
else
System.out.println("No");
}
public static HashSet getSubTree(Node root){
HashSet<String> subTree = new HashSet<String>();
if(root == null)
return subTree;
if(root.left == null && root.right == null){
subTree.add(root.getName());
return subTree;
}
HashSet<String> leftTree = getSubTree(root.left);
String currentTree = "";
int leftTreeSize = 0;
String leftChild = "";
Iterator iteratorLeft = leftTree.iterator();
while(iteratorLeft.hasNext()){
String tmpLeft = iteratorLeft.next().toString();
if(tmpLeft.length() > leftTreeSize){
leftTreeSize = tmpLeft.length();
leftChild = tmpLeft;
}
if(subTree.contains(tmpLeft) && tmpLeft.length() > 1)
subTree.add("Duplicate");
else
subTree.add(tmpLeft);
}
currentTree += leftChild;
currentTree += root.getName();
HashSet<String> rightTree = getSubTree(root.right);
int rightTreeSize = 0;
String rightChild = "";
Iterator iteratorRight = rightTree.iterator();
while(iteratorRight.hasNext()){
String tmpRight = iteratorRight.next().toString();
if(tmpRight.length() > rightTreeSize){
rightTreeSize = tmpRight.length();
rightChild = tmpRight;
}
if(subTree.contains(tmpRight) && tmpRight.length() > 1)
subTree.add("Duplicate");
else
subTree.add(tmpRight);
}
currentTree += rightChild;
if(subTree.contains(currentTree) && currentTree.length() > 1)
subTree.add("Duplicate");
else
subTree.add(currentTree);
return subTree;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment