CTCI 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 T1.

A tree T2 is a subtree if T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut of the tree at node n, the two trees would be identical.

CTCI 4.8.java

public static boolean containsTree(Node root, Node subtree){
    if(root == null) return false;
    if(subtree == null) return true;
    
    if(root.value == subTree.value && ckeckTree(root, subtree)) return true;
    return (containsTree(root.left, subtree) || containsTree(root.right, subtree));
}

public static boolean ckeckTree(Node root, Node subtree){
    if(root == null && subtree == null) return true;
    else if(root == null || subtree == null) return false;
    
    return (root.value == subtree.value && ckeckTree(root.left, subtree.left) && ckeckTree(root.right, subtree.right));
}