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 Tl. A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

CC150-4.8.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 4.8 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 Tl.
	 * A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to
	 * T2. That is, if you cut off the tree at node n, the two trees would be identical.
	 * 
	 * 
	 *  @Runtime & spaces
	 * 	runtime: O(nm) where m is the size of the larger tree and n is the size of the smaller tree
	 * 	space: O(log m + log n)  for recursion calls 
	 * 
	 */
	public boolean containsTree(TreeNode t1,TreeNode t2){
		if(t2==null)
			//the empty tree is always a subtree
			return true;
		return subTree(t1,t2);
	}
	private boolean subTree(TreeNode t1, TreeNode t2) {
		// TODO Auto-generated method stub
		if(t1==null)
			//big tree empty & subtree still not found
			return false;
		if(t1.val==t2.val)
			if(matchTree(t1,t2))
				return true;
		return subTree(t1.left, t2)||subTree(t1.right, t2);
	}
	private boolean matchTree(TreeNode t1, TreeNode t2) {
		// TODO Auto-generated method stub
		if(t1==null&&t2==null)
			return true;
		if(t1==null||t2==null)
			return false;
		if(t1.val!=t2.val)
			return false;
		return (matchTree(t1.left, t2.left))&&(matchTree(t1.right, t2.right));
	}	
}