Is binary tree subtree of another binary tree

Is binary tree subtree of another binary tree

Given two binary trees s and t, find if binary tree t is subtree of binary tree s.
For example: Given binary tree s as follows,
is tree subtree of binary tree
binary tree t will be a subtree as shown.

is subtree of binary tree
target binary tree which is subtree of the source binary tree

However, if the binary tree s is as follows, then t is not a subtree of the tree s

Let’s start from the ver simple cases and build on top of them. What if one of the trees is or both of them are empty? If s and t both are empty binary trees, then of course t is subtree of s.
Other case, when s is empty and t not, then t is not subtree. Similary, when t is not empty and s is empty, then also, t is not subtree of s.

 if(s == null && t == null){
    return true;
 }
        
 if(s == null || t == null){
    return false;
 }

Now, if we start from the root of both trees, there are two possibilities: First, the root of two trees match with values. s.val == t.val. In this case, the problem reduces to check if left subtree of target tree is same as a left subtree of the source and if right subtree of target tree is same as the right subtree of source binary tree.

return s.val == t.val
 && isSame(s.left,t.left)
 && isSame(s.right,t.right);

If everything goes fine and we hit the condition when both s and t then we know that both trees are same and one should be a subtree of other.

Second, the root of the two trees are not the same? In that case, we check if left subtree of s is same as s or right subtree of s is same as t. If one of subtree same as the target tree, we return true.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        
        if(s == null && t == null){
            return true;
        }
        
        if(s != null && t == null){
            return false;
        }
        
        if(s == null && t != null){
            return false;
        }
        
        if(s.val != t.val) {
            return (isSubtree(s.left,t.left) 
                   && isSubtree(s.right,t.right));
        }
        else {
            return  isSubtree(s.left,t)
                    || isSubtree(s.right,t);
        }
    }
}

Above implementation will work for the below case.

but will not work for this case.

This is almost done. But there is one small mistake in it. We are relying on the inequality of the root nodes. What if the current roots are equal and some nodes in left or right subtrees do not the match? We have to come up all the way where we started with s and t to check if t is a subtree of s. That is why we have two separate functions: One to check if trees are same once their roots match and other to start afresh once we find that trees are not the same starting at a particular root. Above function actually does not start from the place where we started with s and t if node values do not match and continue down the subtree. This will return true even if roots and leaves match even if intermediate nodes do not. This is the case most of the students fail to understand.

Binary tree is subtree of another binary tree : Implementation

  
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class IsSubtree {
    public boolean isSubtree(TreeNode s, TreeNode t) {

        if(s == null) return false;
        
        if(!isSame(s,t)){
            return isSubtree(s.left,t)
                   || isSubtree(s.right,t);
        }
        
        return true;
    }
    
    private boolean isSame(TreeNode s, TreeNode t){
        
        if(s == null && t == null){
            return true;
        }
        
        if(s == null || t == null){
            return false;
        }
        
        return s.val == t.val
               && isSame(s.left,t.left)
               && isSame(s.right,t.right);
    }
}

The complexity of implementation to find if one binary tree is a subtree of another is O(n) where n is the number of nodes in the target tree.

You can run this code on the leetcode problem and see it passes all test cases there.
Please share if there is something wrong or missing. If you are preparing for an interview and want personalized coaching, please reach out to us at communications@algorithmsandme.com or book a free session with us.