Subtree of Another Tree

Given two trees, check if the second tree is a subtree of the first tree

For example,

Consider the below trees :

As evident from the diagram , the subRoot tree is a subtree of root.

The input is :

root = [3,4,5,1,2], subRoot = [4,1,2]

The output is true

Try out the solution here:

https://leetcode.com/problems/subtree-of-another-tree/

Solution:

Hint:

Use the algorithm to find if two trees are same or not for this solution.

Explanation:

We have already seen an algorithm to find if two trees are same or not.

We can reuse the same algorithm here.

We can traverse through each node of the root tree recursively and check if the subtree from the current node matches the second tree or not.

We need to do this on each node of the left branch and the right branch of the root node of the first tree.

If any of them matches return true.

Here is the algorithm to find if two trees are same or not:

Here is the entire code to check if a tree is subtree of another:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        
        if(root == null) return false;
        
        
        if(isSameTree(root,subRoot)) return true;
        
        
        return isSubtree(root.left , subRoot) || isSubtree(root.right,subRoot);
        
    }
    
    public boolean isSameTree(TreeNode tree1,TreeNode tree2){
        
        
        if(tree1 == null && tree2 == null) return true;
        
        if(tree1 == null || tree2 == null) return false;
        
        if(tree1.val != tree2.val ) return false;
        
        
        return isSameTree(tree1.left,tree2.left) && isSameTree(tree1.right,tree2.right);
    }
}

Algorithm:

1. If root node is null return false – we need a tree to compare against so if it is not present return false
2. Check if the first and second trees match by using isSameTree() algorithm.
3. If it doesn’t match , recursively check if the second tree is a subtree of the left node of the root node or if it is a subtree of the right node of the root node.

Time complexity:

For every node in the parent tree , we traverse through every node in the subtree recursively in the worst case ,so time complexity is O(m*n) where m is the number of nodes in parent tree and n is number of nodes in second tree.

Space complexity:

For the isSubTree() call we need a recursion stack of memory size n where n is the number of nodes in the parent tree

For the isSameTree() call we need a recursion stack of memory size m where m is the number of nodes in the sub tree.

So total time complexity is O( m + n)