572. Subtree of Another Tree - Solutions and Explanation

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:

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.
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.
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.
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.
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

C++
Java
Python

                            cpp
                            
                        
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;
    }
};

This solution determines if one binary tree is a subtree of another binary tree using C++. The approach involves:

Serializing the two trees into string representations.
Checking if the string representation of the smaller tree (subtree) is a substring of the larger tree (main tree).

Steps:

Convert each tree node to a unique string format by recursively traversing each tree. Utilize markers to denote null nodes to handle edge cases where two different trees might produce similar strings without these markers.
Use the serialized string representation to check if the subtree's serialization is a substring of the main tree's serialization.
Implement substring search using the KMP (Knuth-Morris-Pratt) algorithm, which allows efficient checking through preprocessing of the pattern (subtree serialization) and constructing a longest prefix suffix table to find matches without redundant comparisons.

This approach is efficient in terms of space, as only the serial strings and the prefix table are stored. Also, the time complexity is optimized for searching through the use of the KMP algorithm, making it better than a naive string search approach. This solution provides a comprehensive method to accurately and efficiently determine if one tree is a subtree of another by addressing both structure and node value considerations.

                            java
                            
                        
class Solution {
    public boolean checkSubtree(TreeNode mainTree, TreeNode subTree) {
        // Serialize both trees
        StringBuilder mainSerialized = new StringBuilder();
        serializeTree(mainTree, mainSerialized);
        String mainStr = mainSerialized.toString();

        StringBuilder subSerialized = new StringBuilder();
        serializeTree(subTree, subSerialized);
        String subStr = subSerialized.toString();

        // Use KMP algorithm to check substring
        return runKMP(subStr, mainStr);
    }

    // Function to serialize a tree to string
    private void serializeTree(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#");
            return;
        }
        sb.append("^" + node.val);
        serializeTree(node.left, sb);
        serializeTree(node.right, sb);
    }

    // Implementation of the KMP search algorithm
    private boolean runKMP(String pattern, String text) {
        int pLen = pattern.length();
        int tLen = text.length();
        
        if (tLen < pLen) return false;

        int[] lps = computeLPSArray(pattern, pLen);
        int i = 0;
        int j = 0;

        while (i < tLen) {
            if (pattern.charAt(j) == text.charAt(i)) {
                j++;
                i++;
            }
            if (j == pLen) {
                return true;
            } else if (i < tLen && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return false;
    }

    // Construct longest prefix suffix array for KMP
    private int[] computeLPSArray(String pat, int m) {
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

In the provided Java solution, the task is to determine if one binary tree is a subtree of another binary tree. The approach leverages the serialization of trees and substring search using the Knuth-Morris-Pratt (KMP) algorithm for efficient matching.

Serialize both the main tree and the subtree into strings. This is achieved using a preorder traversal where null nodes are denoted by # and each value is prefixed with ^ to distinguish between different nodes with similar values but different structures.
Use the KMP algorithm to search if the serialized subtree string is a substring of the serialized main tree string. The KMP algorithm provides an efficient way to perform this check, avoiding repeated processing of the text string.
Helper function serializeTree(TreeNode node, StringBuilder sb) handles the serialization of the tree nodes into a string format.
runKMP(String pattern, String text) implements the KMP substring search, which checks if the pattern (serialized subtree) exists within the text (serialized main tree).
computeLPSArray(String pat, int m) constructs the longest prefix which is also suffix array, an essential part of the KMP algorithm to allow efficient pattern matching by avoiding needless re-examination of characters.

The solution efficiently checks if one tree is a subtree of another by converting the tree structure problem into a string pattern recognition problem, utilizing the powerful KMP algorithm tailored for such tasks.

                            python
                            
                        
class Solution:
    def isSubtree(self, mainTree: Optional[TreeNode], subTree: Optional[TreeNode]) -> bool:
        
        # Transform tree into string representation
        def encode(node, result):
            if node is None:
                result.append('*')
                return
            
            result.append('!')
            result.append(str(node.val))
            encode(node.left, result)
            encode(node.right, result)

        # KMP algorithm to find substring
        def stringSearch(sub, main):
            len_sub = len(sub)
            len_main = len(main)

            if len_main < len_sub:
                return False

            lps = [0] * len_sub
            length = 0
            i = 1

            while i < len_sub:
                if sub[i] == sub[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1

            main_index = 0
            sub_index = 0

            while main_index < len_main:
                if main[main_index] == sub[sub_index]:
                    main_index += 1
                    sub_index += 1
                    if sub_index == len_sub:
                        return True
                elif main_index < len_main and sub[sub_index] != main[main_index]:
                    if sub_index != 0:
                        sub_index = lps[sub_index - 1]
                    else:
                        main_index += 1
            
            return False

        # Generate encoded string for trees
        serialized_main_tree = []
        encode(mainTree, serialized_main_tree)
        main_str = ''.join(serialized_main_tree)

        serialized_sub_tree = []
        encode(subTree, serialized_sub_tree)
        sub_str = ''.join(serialized_sub_tree)

        # Search for the encoded subtree in main tree encoding
        return stringSearch(sub_str, main_str)

In solving the problem of checking if one tree is a subtree of another, Python 3 is used to implement a method within a Solution class. The method, named isSubtree, determines if the subTree is a subtree of mainTree. It achieves this by encoding both trees using preorder traversal and subsequently searching for the subtree’s encoded string within the main tree’s encoded string.

Encode each tree to a string:
- A special function encode is used, which recursively converts a tree into a string using preorder traversal. It inserts ! before each node value to ensure unique representations and uses * to denote None values.
Implement string search using Knuth-Morris-Pratt (KMP) algorithm:
- Another function, stringSearch, applies the KMP algorithm to efficiently search for the occurrence of the encoded subTree string within the mainTree string.
- The function prepares a longest prefix which is also suffix (LPS) array to facilitate the pattern matching process.

After encoding both trees and converting them into strings, the isSubtree method utilizes the stringSearch to check if the subTree's encoding is a substring of the mainTree encoding. The solution cleverly shifts the problem from a tree comparison to a string comparison, utilizing the efficiency of the KMP algorithm for matching.

Comments

No comments yet.

Subtree of Another Tree

Problem Statement

Examples

Example 1

Example 2

Constraints

Approach and Intuition

Solutions

Comments

Products

Features

Solutions

Marketplace

Resources

Company

Tech Talks

Vultr Blogs