LeetCode 572: Subtree of Another Tree Solution in Python – A Step-by-Step Guide

Imagine you’re given two binary trees—like a big tree with nodes [3,4,5,1,2] and a smaller one [4,1,2]—and your task is to figure out if the smaller tree is hiding inside the bigger one as an exact copy, with the same structure and values, such as finding that [4,1,2] is indeed a subtree rooted at node 4 in the larger tree. That’s the engaging challenge of LeetCode 572: Subtree of Another Tree, an easy-to-medium problem that’s a fantastic way to practice tree traversal in Python. We’ll explore two solutions: the Best Solution, a recursive subtree matching approach that’s efficient and elegant, and an Alternative Solution, a brute-force traversal with serialization that’s thorough but less optimized. With detailed examples, clear code, and a friendly tone—especially for the recursive method—this guide will help you spot that subtree, whether you’re new to coding or leveling up. Let’s explore those trees and start matching!

What Is LeetCode 572: Subtree of Another Tree?

In LeetCode 572: Subtree of Another Tree, you’re given two binary trees: root (the main tree) and subRoot (the potential subtree), and your task is to return True if subRoot is an identical subtree of root—meaning there’s a node in root where the subtree rooted at that node matches subRoot exactly in structure and values—and False otherwise. For example, with root = [3,4,5,1,2] and subRoot = [4,1,2], True is returned because the subtree at node 4 matches subRoot. This problem builds on LeetCode 100: Same Tree for tree comparison but extends to searching within a larger tree.

Problem Statement

Input: root (TreeNode)—main binary tree; subRoot (TreeNode)—potential subtree.
Output: Boolean—True if subRoot is a subtree of root, False otherwise.
Rules: Subtree must match exactly in structure and values; null nodes included in comparison.

Constraints

Number of nodes in root: 1 to 2000.
Number of nodes in subRoot: 1 to 1000.
Node values: -10⁴ to 10⁴.

Examples

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

Output: True
Tree:

Subtree at 4 matches [4,1,2].

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

Output: False
Tree:

Subtree at 4 has extra 0, no match.

Input: root = [1,1], subRoot = [1]

Output: True
Left child 1 matches [1].

Understanding the Problem: Spotting the Subtree

To solve LeetCode 572: Subtree of Another Tree in Python, we need to determine if subRoot exists as an identical subtree within root, checking both structure and values. With up to 2000 nodes in root, a brute-force approach comparing subRoot at every node could work but might be slow (O(m * n) where m and n are node counts). Instead, a recursive solution efficiently checks each node as a potential match point, reusing a tree comparison function. We’ll explore:

Best Solution (Recursive Subtree Matching): O(m * n) time, O(h) space—fast and elegant (m = nodes in root, n = nodes in subRoot, h = height).
Alternative Solution (Brute-Force Traversal with Serialization): O(m + n) time, O(m + n) space—thorough but complex.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive Subtree Matching

Why Recursive Matching Wins

The recursive subtree matching solution is the best for LeetCode 572 because it efficiently checks for a subtree in O(m * n) time and O(h) space by using two recursive functions: one to traverse root and test each node as a potential match, and another to compare two trees for exact equality, leveraging recursion’s natural fit for tree structures. It’s like exploring a forest, checking each tree to see if it’s an exact replica of the one you’re looking for—all in a streamlined, recursive journey!

How It Works

Think of this as a tree-matching explorer:

Step 1: Define Helper Function:

isSameTree(p, q): Returns True if two trees are identical, False otherwise.

Step 2: Traverse Main Tree:

Recursively visit each node in root.

Step 3: Check Subtree Match:

At each node, call isSameTree with subRoot.

Step 4: Combine Results:

Return True if any node matches, or if left/right subtrees contain a match.

Step 5: Base Case:

If root is None, return False (no match possible).

Why It Works:

Recursion exhaustively checks all nodes.
isSameTree ensures exact structural match.

It’s like a subtree-spotting detective!

Step-by-Step Example

Example: root = [3,4,5,1,2], subRoot = [4,1,2]

Step 1: Define isSameTree:

Base: Null check, value match, recurse left/right.

Step 2: Traverse root:

Node 3:

isSameTree(3, 4): Values differ (3 ≠ 4), False.
Left (4): isSameTree(4, 4):

Left (1, 1): Match.
Right (2, 2): Match.
True, return True.

Right (5): Not needed, already found match.

Result: True.

Example: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]

Step 2: Traverse:

Node 3: isSameTree(3, 4) → False.
Left (4): isSameTree(4, 4):

Left (1, 1): Match.
Right (2, 2): Right of 2 has 0, subRoot has null, False.

Right (5): isSameTree(5, 4) → False.

Step 3: No match found.
Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        # Step 1: Define helper to check if two trees are identical
        def isSameTree(p: TreeNode, q: TreeNode) -> bool:
            if not p and not q:
                return True
            if not p or not q:
                return False
            return (p.val == q.val and 
                    isSameTree(p.left, q.left) and 
                    isSameTree(p.right, q.right))

        # Step 2: Base case - if root is None
        if not root:
            return False

        # Step 3: Check current node and recurse on children
        if isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Lines 10-17: isSameTree:

Base: Both null (True), one null (False).
Recurse: Match values, check left and right.

Lines 20-21: If root null, no match possible.
Lines 24-25: If current node matches subRoot, return True.
Line 26: Recurse on left and right subtrees.
Time Complexity: O(m * n)—each node in root may compare with subRoot.
Space Complexity: O(h)—recursion stack (h = height of root).

It’s like a tree-matching maestro!

Alternative Solution: Brute-Force Traversal with Serialization

Why an Alternative Approach?

The brute-force traversal with serialization converts both trees to strings (e.g., preorder traversal with delimiters), then checks if subRoot’s string is a substring of root’s, running in O(m + n) time and O(m + n) space. It’s thorough but complex due to serialization, making it a good alternative for understanding or when string matching is preferred.

How It Works

Picture this as a tree-string sleuth:

Step 1: Serialize trees to strings with delimiters.
Step 2: Check if subRoot string is in root string.
Step 3: Return result.

It’s like a tree-serializing checker!

Step-by-Step Example

Example: root = [3,4,5,1,2], subRoot = [4,1,2]

Step 1: Serialize:

root: "3,4,1,#,#,2,#,#,5,#,#".
subRoot: "4,1,#,#,2,#,#".

Step 2: Check: "4,1,#,#,2,#,#" in "3,4,1,#,#,2,#,#,5,#,#" → True.
Result: True.

Code for Brute-Force Approach

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#"
            return f",{node.val},{serialize(node.left)},{serialize(node.right)}"

        root_str = serialize(root)
        sub_str = serialize(subRoot)
        return sub_str in root_str

Lines 3-6: Serialize tree with commas and # for null.
Lines 8-10: Convert trees to strings, check substring.
Time Complexity: O(m + n)—serialization and string search.
Space Complexity: O(m + n)—string storage.

It’s a serialization-based matcher!

Comparing the Two Solutions

Recursive Matching (Best):

Pros: O(m * n), O(h), clear logic.
Cons: Recursive overhead.

Serialization (Alternative):

Pros: O(m + n), O(m + n), linear time.
Cons: Serialization complexity.

Recursive matching wins for clarity!

Additional Examples and Edge Cases

root = [1], subRoot = [1]: True.
root = [1,2], subRoot = [2]: True.
Empty trees: Handled by base cases.

Recursive matching handles them all!

Complexity Recap

Recursive: Time O(m * n), Space O(h).
Serialization: Time O(m + n), Space O(m + n).

Recursive’s the elegance champ!

Key Takeaways

Recursive: Tree matching—learn at Python Basics!
Serialization: String trick.
Trees: Subtrees are fun.
Python: Recurse or serialize, your pick!

Final Thoughts: Spot That Subtree!

LeetCode 572: Subtree of Another Tree in Python is a delightful tree challenge. Recursive subtree matching is your fast track, while serialization offers a thorough twist. Want more? Try LeetCode 100: Same Tree or LeetCode 104: Maximum Depth. Ready to explore? Head to Solve LeetCode 572 on LeetCode and find that subtree today!