instagram

Google Interview find if a given binary tree has duplicate sub trees or not

by omt

Find if a given binary tree has duplicate sub trees or not.
(Two leaf nodes of a parent do not count as subtree)

Our tree will be like below.
tree

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;
		}
	}

}
Share