#ctci

SubtreeCheck.java

// since the subtree has only hundreds of nodes while the larger three has millions
// maybe it is better to use BFS instead of DFS to search for the subtree
// since we could end up searching millions of nodes without finding the subtree 
import java.util.Queue;
import java.util.LinkedList;
public SubtreeCheck{
    public boolean isSubtree(Node r1, Node r2){
        if(r1 == null || r2 == null) return false; // discuss with your interviewer
        
        Queue<Node> nodes = new LinkedList<Node>();
        nodes.offer(r1);
        
        Node current = null;
        while(!nodes.isEmpty()){
            current = nodes.poll();
            if(current.val == r2.val && isIdentical(current, r2)) return true;
            if(current.left != null) nodes.offer(current.left);
            if(current.right != null) nodes.offer(current.right);
        }
        return false;
    }
    
    // for this part we can actually use DFS
    private boolean isIdentical(Node r1, Node r2){
        if(r1 == null && r2 == null) return true;
        
        if(r1 != null && r2 == null) return false;
        if(r1 == null && r2 != null) return false;
        
        if(r1.val != r2.val) return false;
        return isIdentical(r1.left, r2.left) && isIdentical(r1.right, r2.right);
    }
}