Subtree of Another Tree

Problem Statement

The given task involves determining if one binary tree is a subtree of another. Specifically, we have two binary trees named root and subRoot. Our goal is to return true if any part of the root tree contains a structure that matches exactly, both in terms of structure and node values, with the subRoot tree. Conversely, if there is no such match, we need to return false.

A "subtree" in this context refers to any node in the root along with all of its descendants, matching exactly in structure and value to the subRoot. The definition also extends to the scenario where a tree can be a subtree of itself.

Examples

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

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

Approach and Intuition

Based on the given problem, here is a structured approach to solving it:

1. Base Case Check:

   • If subRoot is null, it's trivially a subtree of any tree, including an empty tree, so return true.
   • If root is null but subRoot is not, subRoot cannot be a subtree of root, hence return false.

2. Root Matching:

   • Start by comparing the root and subRoot. If they match by value, we potentially have a candidate for a starting point of comparison.

3. Recursive Subtree Matching:

   • Use a recursive function to check if the tree rooted at the current root node matches the subRoot.
   • This involves matching the root values of both trees and recursively ensuring both left and right subtrees also match.

4. Further Searching:

   • Even if the current root node does not match subRoot, the required subtree might exist deeper in either the left or right subtree of the current root.
   • Recursively apply the same check to the left and right children of the root.

5. Return Result:

   • Any of the above steps, if yielding a true, would mean subRoot is a subtree of root. The operation concludes once either a match is found or all nodes are checked.

This approach ensures that every node of the main tree is compared against the sub-root potentially being a start of the matching subtree, thus covering all possibilities within the constraints provided. The constraint that the number of nodes in the root can go up to 2000 and subRoot up to 1000 makes a purely recursive solution feasible but suggests the necessity for efficient handling to prevent excessive recursive calls.

Solutions

class Solution {
public:
    bool checkSubtree(TreeNode* mainRoot, TreeNode* subRoot) {
        string mainTree = "";
        serializeTree(mainRoot, mainTree);
        string subTree = "";
        serializeTree(subRoot, subTree);
            
        return substringSearch(subTree, mainTree);
    }
        
    void serializeTree(TreeNode* node, string& result) {
        if (!node) {
            result += "#";
            return;
        }
    
        result += "^";
        result += to_string(node->val);
        serializeTree(node->left, result);
        serializeTree(node->right, result);
    }
    
    bool substringSearch(string needle, string haystack) {
        int needleLen = needle.size();
        int haystackLen = haystack.size();
            
        if (haystackLen < needleLen)
            return false;
            
        vector<int> longestPrefixSuffix(needleLen, 0);
        int length = 0;
        int i = 1;
            
        while (i < needleLen) {
            if (needle[i] == needle[length]) {
                length++;
                longestPrefixSuffix[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = longestPrefixSuffix[length - 1];
                } else {
                    longestPrefixSuffix[i] = 0;
                    i++;
                }
            }
        }
            
        int mainIdx = 0;
        int subIdx = 0;
            
        while (mainIdx < haystackLen) {
            if (needle[subIdx] == haystack[mainIdx]) {
                subIdx++;
                mainIdx++;
                if (subIdx == needleLen) return true;
            } else {
                if (subIdx != 0) {
                    subIdx = longestPrefixSuffix[subIdx - 1];
                } else {
                    mainIdx++;
                }
            }
        }
            
        return false;
    }
};