572. Subtree of Another Tree

Problem Link

To check whether one tree is a subtree of another, the main challenge is comparing both structure and values efficiently. A direct recursive comparison at every node can work, but it's inefficient to check if both subtrees are the same tree for every matching tree in the worst case. Instead, we can hash both trees in string and reframe the problem as a string-matching task.

You can serialize both trees as a string using any standard traversal algorithms, just make sure the null child nodes are noted in serialization Including null markers is crucial without them, different tree structures could produce the same string.

Once both trees are serialized, the problem reduces to checking whether the serialized subRoot string appears as a substring within the serialized root string.

To perform this check efficiently, we use the Z-algorithm. We concatenate the strings as subRoot_serialized + "|" + root_serialized and compute the Z-array. The Z-value at a position tells us how many characters match the prefix starting from that index.

If at any position in the concatenated string the Z-value equals the length of the serialized subRoot, we have found an exact match, meaning the subtree exists.

This approach ensures that both tree structure and node values are matched exactly, while achieving linear-time string matching.

Pseudocode

function isSubtree(root, subRoot):
    s = serialize(subRoot)
    t = serialize(root)
    z = Z_function(s + "|" + t)
    for i from len(s)+1 to end:
        if z[i] == len(s):
            return true
    return false

Runtime Complexity

Time: \(O(n + m)\), where \(n\) and \(m\) are the number of nodes in root and subRoot

Space: \(O(n + m)\) for serialization and Z-array

PythonGo

class Solution:
    def z_function(self, s: str) -> list[int]:
        n = len(s)
        z = [0]*n
        l=r=0
        for i in range(1, n):
            if i > r:
                l=r=i
                while r < n and s[r] == s[r-l]:
                    r+=1
                z[i] = r-l
                r-=1
            else:
                k = i-l
                if z[k] < r-i+1:
                    z[i] = z[k]
                else:
                    l = i
                    while r < n and s[r] == s[r-l]:
                        r+=1
                    z[i] = r-l
                    r-=1
        return z

    def _seralize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return "$N"
        return f"${root.val}{self._seralize(root.left)}{self._seralize(root.right)}"

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        substr = self._seralize(subRoot)
        text = self._seralize(root)
        z = self.z_function(f"{substr}|{text}")
        k = len(substr)
        for i in range(len(text)):
            if z[i+k+1] == k:
                return True
        return False

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    var serialize func(node *TreeNode) string
    serialize = func(node *TreeNode) string {
        if node == nil {
            return "#$"
        }
        return "#" + strconv.Itoa(node.Val) + serialize(node.Left) + serialize(node.Right)
    }

    var z_func func(s string) []int
    z_func = func(s string) []int {
        n := len(s)
        z := make([]int, n)
        l, r := 0, 0
        for i := 1; i < n; i++ {
            if i > r {
                l, r = i, i
                for r < n && s[r] == s[r-l] {
                    r++
                }
                z[i] = r - l
                r--
            } else {
                k := i - l
                if z[k] < r-i+1 {
                    z[i] = z[k]
                } else {
                    l = i
                    for r < n && s[r] == s[r-l] {
                        r++
                    }
                    z[i] = r - l
                    r--
                }
            }
        }
        return z
    }

    substr, str := serialize(subRoot), serialize(root)

    z := z_func(substr + "|" + str)
    k := len(substr)
    for i := 0; i < len(str); i++ {
        if z[i+k+1] == k {
            return true
        }
    }
    return false
}

---