💬 Discord
Sign In
NeetCode #391LC-572EasyTreesBlind 75NC 150NC 250
← Back to All Problems

#391 · #572 · Subtree of Another Tree(另一棵树的子树)

📌 Problem Statement & Constraints

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. Constraints: the number of nodes in root is in [1, 2000], in subRoot in [1, 1000].

💡 Core Algorithmic Approaches

  1. For every node of root, test whether the subtree rooted there is identical to subRoot (using the Same Tree check).
  2. Recurse into both children until a match is found or the tree is exhausted.
  3. This is O(m * n) in the worst case, which the constraints allow.
  4. A linear alternative serialises both trees with explicit null markers and searches for the pattern, using KMP to avoid a quadratic substring search.

💻 Benchmark Python3 Implementation

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not root:
            return False
        # try matching here, or in either subtree
        return (self._same(root, subRoot)
                or self.isSubtree(root.left, subRoot)
                or self.isSubtree(root.right, subRoot))

    def _same(self, a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
        if not a and not b:
            return True
        if not a or not b:
            return False
        return (a.val == b.val
                and self._same(a.left, b.left)
                and self._same(a.right, b.right))


# Linear alternative: serialise both trees with null markers, then substring search
class Solution2:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def ser(node: Optional[TreeNode]) -> str:
            if not node:
                return ",#"
            # the leading comma delimits values so that "1" does not match "12"
            return "," + str(node.val) + ser(node.left) + ser(node.right)

        return ser(subRoot) in ser(root)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n) for the straightforward version, where m and n are the tree sizes. The serialisation version is O(m + n) with KMP (or O(m * n) with naive substring search).
💾 Space Complexity
O(h) for the recursion stack; O(m + n) for the serialisation version.

⚠️ Interview Pitfalls & Follow-ups

  • Serialising without delimiters: the values 1 and 12 would create false matches; the leading comma prevents that.
  • Using the null marker without a separator: # and ,# can be confused, so a consistent delimiter is needed.
  • Forgetting that subRoot may equal the whole tree: the match check at the current node covers that.
  • Assuming subRoot is never empty: the constraints guarantee at least one node, but the empty case would trivially return true.