Check if a binary tree is subtree of another binary tree

Check if a binary tree is subtree of another binary tree.

---

Given two binary trees, check if the first tree is subtree of the second one. 
A tree is called subtree if all the nodes and its child of the subtree(S) is present in Tree(T) in the same structure.

Lets understand what is the input and the expected output.

Algorithm 

---

If we know how to check if two trees are identical then it is very easy to check if tree is subtree of another. 

I would suggest to go through below article,

1. Check if two trees are identical or not
2. Check if two trees are mirror images of each other
   

We just need to find the first matching node in Tree(T) that matches with the root node of subtree(S), once we find that, our problem narrows down to find if two trees are identical.

Check if a binary tree is subtree of another tree in Java. 

---

BinaryTreeIsSubtree.java

package com.javabypatel.tree;

public class BinaryTreeIsSubtree {
   
    public static void main(String[] args) {
        new BinaryTreeIsSubtree();
    }
 
    public BinaryTreeIsSubtree() {

        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

            /*

                     50
                  /      \
                 30       70
               /   \     /  \
              20   40   60  80
             /  \
            10  25

            */


        Node subtree = null;
        subtree = addNode(subtree, 30);
        subtree = addNode(subtree, 20);
        subtree = addNode(subtree, 40);
        subtree = addNode(subtree, 10);
        subtree = addNode(subtree, 25);
        /*
                 30
               /   \
              20   40
             /  \
            10  25
        */

        System.out.println(checkIfTreeIsSubtree(rootNode, subtree));
    }

    private boolean checkIfTreeIsSubtree(Node rootNode, Node subtree) {
        if(subtree == null) {
            return true;
        }
        if(rootNode == null) {
            return false;
        }

        if(rootNode.getData() == subtree.getData()) {
            return checkIfTreeIsIdentical(rootNode, subtree);
        } else {
            return checkIfTreeIsSubtree(rootNode.getLeft(), subtree) ||
                checkIfTreeIsSubtree(rootNode.getRight(), subtree);
        }
    }

    private boolean checkIfTreeIsIdentical(Node rootNode, Node subtree) {
        if (rootNode == null && subtree == null) {
            return true;
        }
        if (rootNode == null || subtree == null) {
            return false;
        }

        if(rootNode.getData() != subtree.getData()) {
            return false;
        }

        return checkIfTreeIsIdentical(rootNode.getLeft(), subtree.getLeft()) &&
            checkIfTreeIsIdentical(rootNode.getRight(), subtree.getRight());

    }

    private Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);
 
            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}

Node.java

package com.javabypatel.tree;

public class Node {
    private int data;
    private Node left;
    private Node right;
 
    public Node(int data) {
        this.data = data;
    }
 
    public int getData() {
        return data;
    }
 
    public void setData(int data) {
        this.data = data;
    }
 
    public Node getLeft() {
        return left;
    }
 
    public void setLeft(Node left) {
        this.left = left;
    }
 
    public Node getRight() {
        return right;
    }
 
    public void setRight(Node right) {
        this.right = right;
    }
}

You may also like to see

---

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.