Google Interview find if a given binary tree has duplicate sub trees or not
Find if a given binary tree has duplicate sub trees or not.
(Two leaf nodes of a parent do not count as subtree)
Algorithm
import java.util.Set; import java.util.TreeSet; import com.omt.learn.algo.util.tree.TreeNode; public class DuplicateTreeInTree { public static void main(String[] args) { System.out.println("Is Duplicate Sub Trees :" + isContainsDuplicateTrees(generateTree())); } public static boolean isContainsDuplicateTrees(TreeNode root) { return isContainsDuplicateTrees(new TreeSet<>(), root); } public static boolean isContainsDuplicateTrees(Set<String> trees, TreeNode root) { if (root != null) { String tree = ""; if (root.leftNode != null) { tree += root.leftNode.nodeName; } tree += root.nodeName; if (root.rightNode != null) { tree += root.rightNode.nodeName; } if (trees.contains(tree)) { System.out.println(tree); return true; } if (tree.length() == 3) { System.out.println(tree); trees.add(tree); } boolean isLeftHave = false; if (root.leftNode != null) { isLeftHave = isContainsDuplicateTrees(trees, root.leftNode); } boolean isRightHave = false; if (root.rightNode != null) { isRightHave = isContainsDuplicateTrees(trees, root.rightNode); } return (isLeftHave || isRightHave); } return false; } public static TreeNode generateTree() { TreeNode AVL = new TreeNode(new TreeNode(new TreeNode("D"), new TreeNode("E"), "B"), new TreeNode(new TreeNode("I"), new TreeNode(new TreeNode("H"), new TreeNode(new TreeNode("D"), new TreeNode("E"), "B"), "F"), "C"), "A"); return AVL; } }
TreeNode.java
public class TreeNode { public String nodeName = ""; public boolean isVisited = false; public int value = 0; public TreeNode leftNode = null; public TreeNode rightNode = null; public TreeNode parentNode = null; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(String name) { nodeName = name; } public TreeNode(TreeNode left, TreeNode right, String name) { leftNode = left; rightNode = right; nodeName = name; setParent(); } private void setParent() { if (leftNode != null) { leftNode.parentNode = this; } if (rightNode != null) { rightNode.parentNode = this; } } }