Subtree of Another Tree easy

Problem Statement

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 as subRoot and false otherwise. A subtree of a binary tree root is a tree that consists of a node in root and all of this node's descendants. The tree root may contain multiple subtrees of the same structure and node values as subRoot.

Example 1

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

Example 2

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

Steps

1. Recursive Check: The core idea is to recursively check if the subtree rooted at each node in root matches subRoot.
2. Base Cases:
   • If subRoot is empty (nullptr), it's considered a match (an empty subtree is a subtree of any tree).
   • If root is empty (nullptr) and subRoot is not, there's no match.
3. Recursive Calls: If both root and subRoot are not empty, compare their values. If they match, recursively compare their left and right subtrees.
4. Subtree Check: If the values match and the recursive checks for the left and right subtrees return true, we've found a matching subtree.
5. Iterate Through root: The function iterates through each node in root as a potential starting point for a matching subtree.

Explanation

The solution uses a recursive helper function isSameTree to compare two trees for structural and value equality. The main function then iterates through the nodes of the root tree, using isSameTree to check if the subtree starting at each node matches subRoot. If a match is found, it returns true; otherwise, after checking all nodes, it returns false.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (subRoot == nullptr) return true; // Empty subRoot always matches
        if (root == nullptr) return false; // root empty, subRoot not empty, no match

        // Check if the subtree rooted at the current node matches subRoot
        if (isSameTree(root, subRoot)) return true;

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

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

Complexity

• Time Complexity: O(M * N), where N is the number of nodes in root and M is the number of nodes in subRoot. In the worst case, we might compare subRoot with every subtree in root.
• Space Complexity: O(max(H1, H2)), where H1 is the height of root and H2 is the height of subRoot. This space is used for the recursion stack. In the worst case, this could be proportional to the height of the larger tree.