Java: Subtree of Another Tree

Thought Process

The problem requires checking if the 'subRoot' tree is a subtree of the root tree or not. To solve this, we use a helper function 'areSameTree' to check if two trees are identical. We then recursively check if the 'subRoot' matches any subtree of the root. If a match is found, we return true; otherwise, we return false. 

/**
 * 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 areSameTree(TreeNode root, TreeNode subRoot){

        if(root==null && subRoot == null)
            return true;
        else if(root == null || subRoot==null)
            return false;
    
        return (root.val == subRoot.val 
                && areSameTree(root.left,subRoot.left) 
                && areSameTree(root.right,subRoot.right));
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        if(root== null && subRoot==null)
            return true;
        
        if(root==null || subRoot==null)
            return false;

        if(areSameTree(root,subRoot))
            return true;
        else
            return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
}

Code Complexity

Time Complexity: O(n * m)

The algorithm checks each node of the root tree against the subRoot tree, where 'n' is the number of nodes in the root tree and 'm' is the number of nodes in the subRoot tree.

Space Complexity: O(h)

The algorithm uses recursion, and the space complexity depends on the height h of the root tree due to the call stack.

Code copied!