Determine if a small tree is the subtree of a huge tree

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

My initial thoughts:
Let us denote the huge tree as T1 and the small tree as T2. We iterate through T1 to see if any node matches the root node of T2. If there’s match, we check if the subtree of T1 is identical to T2. If not, we recursively go deeper.

My initial codes:

	public static boolean isSubtree(BinaryTreeNode<Integer> T1,
			BinaryTreeNode<Integer> T2) {
		if (T1 == null)
			return false;
		else if (T1.getValue().equals(T2.getValue()) && isTwoTreeEqual(T1, T2)) {
			return true;
		} else {
			return isSubtree(T1.getLeft(), T2) || isSubtree(T1.getRight(), T2);
		}
	}

	public static boolean isTwoTreeEqual(BinaryTreeNode<Integer> root1,
			BinaryTreeNode<Integer> root2) {
		if (root1 == null && root2 == null)
			return true;
		else if (root1.isLeaf() && root2.isLeaf())
			return root1.getValue().equals(root2.getValue());
		else if (!root1.isLeaf() && !root2.isLeaf()) {
			if (!root1.getValue().equals(root2.getValue()))
				return false;
			return isTwoTreeEqual(root1.getLeft(), root2.getLeft())
					&& isTwoTreeEqual(root1.getRight(), root2.getRight());
		} else
			return false;
	}

Comments after running:
It works for small trees. When the size goes to 1000, it nearly never finishes. BAD.

Solutions:

	public static boolean containsTree(BinaryTreeNode<Integer> t1,
			BinaryTreeNode<Integer> t2) {
		if (t2 == null)
			return true; // The empty tree is always a subtree
		else
			return subTree(t1, t2);
	}

	private static boolean subTree(BinaryTreeNode<Integer> r1,
			BinaryTreeNode<Integer> r2) {
		if (r1 == null)
			return false; // big tree empty & subtree still not found.
		if (r1.getValue() == r2.getValue()) {
			if (matchTree(r1, r2))
				return true;
		}
		return (subTree(r1.getLeft(), r2) || subTree(r1.getRight(), r2));
	}

	private static boolean matchTree(BinaryTreeNode<Integer> r1,
			BinaryTreeNode<Integer> r2) {
		if (r2 == null && r1 == null)
			return true; // nothing left in the subtree
		if (r1 == null || r2 == null)
			return false; // big tree empty & subtree still not found
		if (r1.getValue() != r2.getValue())
			return false; // data doesn’t match
		return (matchTree(r1.getLeft(), r2.getLeft()) && matchTree(
				r1.getRight(), r2.getRight()));
	}

The solution is very similar to mine except that it handles the case where T2 is null.

Advertisements

1 Comment (+add yours?)

  1. Saad Shakil
    Mar 13, 2013 @ 15:44:01

    Thank you for a great implementation!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: