Checking if a given binary tree is a sub-tree of another binary tree.

Q. 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.

Algorithm:

1. Traverse T1, find nodes that match the root of T2.

2. For all the nodes that match, check if the trees with those roots are equivalent. 

Source:

import java.util.ArrayList;
import java.util.List;

class Code{
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
        
        @Override
        public boolean equals(Object o){
            return o.hashCode() == this.hashCode();
        }

        @Override
        public int hashCode() {
            return value;
        } 
    }
    
    private void getIdenticals(Node node, Node B, List<Node> store){
        if(node==null) return;
        if(node.equals(B)) store.add(node);
        getIdenticals(node.left, B, store);
        getIdenticals(node.right, B, store); 
    }
    
    public boolean isSubtree(Node root, Node B){ 
        if(root == null || B == null)return false;
        List<Node> possibleNodes = new ArrayList<>();
        getIdenticals(root, B, possibleNodes);
        for(Node n:possibleNodes)
            if(match(n, B))return true;
        return false;
    }
    
    private boolean match(Node head, Node B){
        if(head==null && B == null)return true;
        if(head==null || B == null)return false;
        if(head.equals(B)){
            if(match(head.left, B.left) && match(head.right, B.right)) return true;
        }
        return false;
    }
    
    Node root;
    Node A, B;
    
    public void buildCustomTree(){
        A = root = new Node(5);
        setChildren(root, 7, 6);
        setChildren(root.left, 8, 10);
        setChildren(root.left.right, 12, 13);
        setChildren(root.left.right.left, 14, null);
        setChildren(root.left.right.right, null, 15);
        setChildren(root.left.right.right.right, 16, 17);
        setChildren(root.left.right.right.right.left, null, 18);
        setChildren(root.right, null, 11);
        
        B = new Node(13);
        setChildren(B, null, 15);
        setChildren(B.right, 16, 17);
        setChildren(B.right.left, null, 18); 
    }
    
    private void setChildren(Node node, Integer left, Integer right){
        if(left!=null)node.left = new Node(left);
        if(right!=null)node.right = new Node(right);
    }
    
    public static void main(String[] args){
        Code tree = new Code();
        tree.buildCustomTree();
        System.out.println(tree.isSubtree(tree.A, tree.B));
    }
}

Output:

true