Skip to content

572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values ofsubRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

img

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

img

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Solution:

/**
 * 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 (subRoot == null){
            return true;
        }

        if (isSameTree(root, subRoot)){
            return true;
        }

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }

    public boolean isSameTree(TreeNode root, TreeNode subRoot){
        if (root == null && subRoot == null){
            return true;
        }

        if (root == null && subRoot != null){
            return false;
        }

        if (root != null && subRoot == null){
            return false;
        }

        if (root.val != subRoot.val){
            return false;
        }

        return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }
}

//TC:O(n*m)
//SC:O(n+m)

Complexity Analysis

  • Time complexity: O(MN). For every N node in the tree, we check if the tree rooted at node is identical to subRoot. This check takes O(M)time, where M is the number of nodes in subRoot. Hence, the overall time complexity is O(MN).

  • Space complexity: O(M+N).

There will be at most N recursive call to dfs ( or isSubtree). Now, each of these calls will have M recursive calls to isIdentical. Before calling isIdentical, our call stack has at most O(N) elements and might increase to O(N+M) during the call. After calling isIdentical, it will be back to at most O(N) since all elements made by isIdentical are popped out. Hence, the maximum number of elements in the call stack will be M+N.