Subtree of Another Tree

Problem Description

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 of subRoot, 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 can also be considered as a subtree of itself.

Examples

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].
• -10⁴ ≤ root.val ≤ 10⁴
• -10⁴ ≤ subRoot.val ≤ 10⁴

Checking for Identical Trees at Every Candidate Node

A tree subRoot is a subtree of root if we can find a node in root such that the tree rooted at that node is identical to subRoot.

This requires a two-level recursion:

1. Traverse the root tree. For every node encountered, we check if the tree starting at this node is identical to subRoot (reusing the logic from the “Same Tree” problem).
2. If the check succeeds, we return true. If it fails, we recursively check the left and right children of root to see if subRoot matches further down.

Solution 1: Double Recursion (DFS)

Check if the current root matches subRoot using a helper function. If not, recurse on root.left and root.right.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false; // subRoot cannot be a subtree of null

        // if they match at this level, we are done
        if (isSameTree(root, subRoot)) return true;

        // search left and right subtrees
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False  # subRoot cannot be a subtree of null

        # if they match at this level, we are done
        if self.isSameTree(root, subRoot):
            return True

        # search left and right subtrees
        return self.isSubtree(root.left, subRoot) or self.isSubtree(
            root.right, subRoot
        )

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

class Solution {
private:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }

public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false; // subRoot cannot be a subtree of null

        // if they match at this level, we are done
        if (isSameTree(root, subRoot)) return true;

        // search left and right subtrees
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

Complexity Analysis:

• Time Complexity: O(s * t) in the worst case, where s is the number of nodes in root and t is the number of nodes in subRoot. For each of the s nodes, we might perform a comparison that takes up to t steps.
• Space Complexity: O(h_s) where h_s is the height of the root tree, representing the recursive call stack depth.

Where it breaks: The worst-case time complexity is O(s * t) when there are many nodes in root that have the same value as the root of subRoot. To optimize to O(s + t), we can serialize both trees into strings and use string matching algorithms (like KMP), though this is significantly harder to write during an interview.

Common Mistakes

• Returning true when root is null. If root is null and subRoot is not null, subRoot cannot be a subtree. The base case must return false.
• Calling isSubtree(root.left, subRoot.left) instead of isSubtree(root.left, subRoot). In the outer recursion, you are searching for the entire subRoot tree inside the subtrees of root, so the second argument must remain subRoot.
• Failing to check structure matching strictly. A subtree requires that all descendants match. If root has extra nodes below the matching structure, it is not a valid subtree match.

Frequently Asked Questions

Can a tree be a subtree of itself? Yes. By definition, a tree is considered a subtree of itself, which is handled correctly by the isSameTree(root, subRoot) check at the very first call.

Is there a way to solve this in O(s + t) time? Yes. You can serialize both trees using pre-order traversal (including null markers) into strings, and then check if the serialized subRoot string is a substring of the serialized root string using the KMP or Rabin-Karp algorithm.

What does this problem test in interviews? It tests your ability to write modular recursive code (reusing the Same Tree helper) and navigate nested recursive functions.

← All Problems