Question4_8.java

/**
 * 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 of T1 if there exists a node n in T1 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.
 * 
 * Time  Complexity: O(mn) (worst case)
 * Space Complexity: O(logm + logn)
 */

public class Question4_8 {
    public boolean isSubtree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        } else if (root1 == null) {
            return false;
        }
        
        return equalNode(root1, root2) || isSubtree(root1.left, root2) || isSubtree(root1.right, root2);
    }
    
    
    private boolean equalNode(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return node1 == null && node2 == null;
        }
        
        if (node1.value == node2.value) {
            return equalNode(node1.left, node2.left) && equalNode(node1.right, node2.right);
        } else {
            return false;
        }
    }
    
    
    public static void main(String[] args) {
        Question4_8 question4_8 = new Question4_8();
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.right = new TreeNode(5);
        root1.right.right = new TreeNode(6);
        root1.left.right.left = new TreeNode(7);
        TreeNode root2 = new TreeNode(3);
        System.out.println(question4_8.isSubtree(root1, root2));
        root2.right = new TreeNode(6);
        System.out.println(question4_8.isSubtree(root1, root2));
        root2 = new TreeNode(2);
        root2.right = new TreeNode(5);
        root2.left = new TreeNode(4);
        root2.right.left = new TreeNode(77);
        System.out.println(question4_8.isSubtree(root1, root2));
        root2.right.left.value = 7;
        System.out.println(question4_8.isSubtree(root1, root2));
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}