Check if a binary tree is subtree of another binary tree

In this article, we will implement the algorithm to check if a given binary tree is the subtree of another binary tree in Java.

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

As we know, a binary tree can be constructed with its inorder and preorder traversal combined. Hence, the algorithm for this particular problem is to first find the inorder and preorder traversal of both the given binary tree and if the inorder and preorder traversal of the subtree is a subset of inorder and preorder traversal of the main tree respectively then the given tree is a subtree of the main tree.

Let us assume below tree:

Here the inorder and preorder traversal of the subtree is the subset of given main tree. Hence, we can say that the tree S is a subtree of tree T as tree S consisting of node 7 of tree T and all of the descendants of it.

Binary Tree Node Implementation

Below is the Java implementation of our binary tree. The node itself has two nodes as left and right child.

public class BinaryTreeNode {

    private int data;
    private BinaryTreeNode leftNode;
    private BinaryTreeNode rightNode;

Below is the Java program that implements the above algorithm.

public class SubtreeCheck {

    public static boolean checkSubtree(BinaryTreeNode root, BinaryTreeNode subtree){
        if (subtree == null){
            return true;
        }
        if (root == null){
            return false;
        }
        List rootInOrderList = new ArrayList<>();
        List rootPreOrderList = new ArrayList<>();

        List subtreeInOrderList = new ArrayList<>();
        List subTreePreOrderList = new ArrayList<>();
        
        inOrderTraversal(root, rootInOrderList);
        preOrderTraversal(root, rootPreOrderList);

        inOrderTraversal(subtree, subtreeInOrderList);
        preOrderTraversal(subtree, subTreePreOrderList);

        String mainTreeInOrder = convertToString(rootInOrderList);
        String mainTreePreOrder = convertToString(rootPreOrderList);

        String subTreeInOrder = convertToString(subtreeInOrderList);
        String subTreePreOrder = convertToString(subTreePreOrderList);

        System.out.println(mainTreeInOrder);
        System.out.println(mainTreePreOrder);

        System.out.println(subTreeInOrder);
        System.out.println(subTreePreOrder);

        boolean subTree = mainTreeInOrder.contains(subTreeInOrder) && mainTreePreOrder.contains(subTreePreOrder);
        System.out.println("Is given tree a subtree " + subTree);
        return subTree;
    }

    private static String convertToString(List rootPreOrder) {
        StringBuilder result = new StringBuilder();
        rootPreOrder.stream().forEach(data -> result.append(data));
        return result.toString();
    }

    private static void preOrderTraversal(BinaryTreeNode node, List list) {
        if (node != null) {
            list.add(node.getData());
            preOrderTraversal(node.getLeftNode(), list);
            preOrderTraversal(node.getRightNode(), list);
        }
    }

    private static void inOrderTraversal(BinaryTreeNode node, List list) {
        if (node != null) {
            inOrderTraversal(node.getLeftNode(), list);
            list.add(node.getData());
            inOrderTraversal(node.getRightNode(), list);
        }
    }

    public static void main(String[] args){

        BinaryTreeNode main = new BinaryTreeNode(15);
        main.setLeftNode(new BinaryTreeNode(7));
        main.getLeftNode().setLeftNode(new BinaryTreeNode(5));
        main.getLeftNode().setRightNode(new BinaryTreeNode(10));
        main.getLeftNode().getRightNode().setLeftNode(new BinaryTreeNode(8));

        main.setRightNode(new BinaryTreeNode(30));
        main.getRightNode().setLeftNode(new BinaryTreeNode(25));
        main.getRightNode().setRightNode(new BinaryTreeNode(35));


        BinaryTreeNode subTree = new BinaryTreeNode(15);
        subTree.setLeftNode(new BinaryTreeNode(7));
        subTree.getLeftNode().setLeftNode(new BinaryTreeNode(5));
        subTree.getLeftNode().setRightNode(new BinaryTreeNode(10));
        subTree.getLeftNode().getRightNode().setLeftNode(new BinaryTreeNode(8));

        SubtreeCheck.checkSubtree(main, subTree);
    }
}

Conclusion

In this article, we implemented the algorithm to check if a given binary tree is the subtree of another binary tree or not.