Created
March 9, 2017 20:20
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* | |
* @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