Write java code to find that a given binary tree is a subtree of another binary tree

There are two binary tree and you have to find that , one of the binary tree is the sub-tree in another binary tree.

We have three cases here.

1. The root of subtree matches with the root of binary tree.
2. If above condition fails, We look into left-subtree of the main binary tree to find out if the given binary tree is a sub-tree or not.
3. If above conditionos fail, then we do the sub-tree comparison in the right-subtree

This is the entire algorithm. You can watch me code the solution for this problem on youtube.

I have two functions, which does the real job.
One of those are isSubTree .. This is entry point in the execution of the algorithm.
It recursively calls itself to iterate over left and right sub-tree.
It delegates the main comparison work to allTheNodesMatches function.

private static boolean isSubTree(final BinaryTreeNode rootOfMainTree, final BinaryTreeNode rootOfSubTree){
        if(rootOfSubTree == null && rootOfMainTree == null) return true;
        if(rootOfSubTree == null || rootOfMainTree == null) return false;

    return allTheNodesMatches(rootOfMainTree, rootOfSubTree) || 
           isSubTree(rootOfMainTree.left, rootOfSubTree)     || 
           isSubTree(rootOfMainTree.right, rootOfSubTree);
    }

In the allTheNodesMatches function, we compare the values of nodes from both the tree. The logic behind splitting the code in different function is to isolate the idea of difference between main binary tree and smaller binary tree or the binary tree under test. In the allTheNodesMatches function, you can see that we do not treat the root nodes of two different binary tree differently.

private static boolean allTheNodesMatches(final BinaryTreeNode rootOfMainTree, final BinaryTreeNode rootOfSubTree){
        if(rootOfSubTree == null && rootOfMainTree == null) return true;
        if(rootOfSubTree == null || rootOfMainTree == null) return false;

    return rootOfSubTree.data == rootOfMainTree.data && 
           allTheNodesMatches(rootOfMainTree.left, rootOfSubTree.left) && 
           allTheNodesMatches(rootOfMainTree.right, rootOfSubTree.right);  

    }

Both the nodes rootOfMainTree and rootOfSubTree have no functional differences. If we look at the code, we can see that we are just comparing two different binary trees. We are not looking to find a sub-tree.

So, now we have our working functions with us. It is time to put rest of the code to run the test.

The complete code is written below,  while you can browse or read my code on  github for better reading experience.

public class CheckBTree{

    private static int height(final BinaryTreeNode root){
        return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));
    }

    private static void printBinaryTreeNode(final BinaryTreeNode node){
        if(node == null) System.out.println("NULL Node");

    System.out.format("[%d] ", node.data);
    }
    private static class BinaryTreeNode{
        private int data;
        private BinaryTreeNode left;
        private BinaryTreeNode right;
    
        private BinaryTreeNode(final int data, final BinaryTreeNode left, final BinaryTreeNode right){
            this.data  = data;
    	this.left  = left;
    	this.right = right;
        }
        private BinaryTreeNode(final int data){
            this(data, null, null);
        }
    }
    
    public static void main(final String[] args){
        final BinaryTreeNode one   = new BinaryTreeNode(1);
        final BinaryTreeNode two   = new BinaryTreeNode(2);
        final BinaryTreeNode three = new BinaryTreeNode(3);
        final BinaryTreeNode four  = new BinaryTreeNode(4);
        final BinaryTreeNode five  = new BinaryTreeNode(5);
        final BinaryTreeNode six   = new BinaryTreeNode(6);
    
        four.left = one;
        four.right = five;
    
        five.right = six;
    
        one.left = two;
        one.right = three;

        final BinaryTreeNode one_subTree   = new BinaryTreeNode(1);
        final BinaryTreeNode two_subTree   = new BinaryTreeNode(2);
        final BinaryTreeNode three_subTree = new BinaryTreeNode(3);

        one_subTree.left = two_subTree;
        one_subTree.right = three_subTree;

    if(isSubTree(four, one_subTree)) System.out.println("Subtree exists");
        else System.out.println("Subtree does not exists");

        one_subTree.left = two_subTree;
        one_subTree.right =  null;

    if(isSubTree(four, one_subTree)) System.out.println("Subtree exists");
        else System.out.println("Subtree does not exists");
    }

    private static boolean allTheNodesMatches(final BinaryTreeNode rootOfMainTree, final BinaryTreeNode rootOfSubTree){
        if(rootOfSubTree == null && rootOfMainTree == null) return true;
        if(rootOfSubTree == null || rootOfMainTree == null) return false;

    return rootOfSubTree.data == rootOfMainTree.data && 
           allTheNodesMatches(rootOfMainTree.left, rootOfSubTree.left) && 
           allTheNodesMatches(rootOfMainTree.right, rootOfSubTree.right);  

    }

    private static boolean isSubTree(final BinaryTreeNode rootOfMainTree, final BinaryTreeNode rootOfSubTree){
        if(rootOfSubTree == null && rootOfMainTree == null) return true;
        if(rootOfSubTree == null || rootOfMainTree == null) return false;

    return allTheNodesMatches(rootOfMainTree, rootOfSubTree) || 
           isSubTree(rootOfMainTree.left, rootOfSubTree)     || 
           isSubTree(rootOfMainTree.right, rootOfSubTree);
    }
}