Pseudo-code:

text
function isSubtree(root, subRoot):
    if root is null: return false
    if isSameTree(root, subRoot): return true
    return isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot)

function isSameTree(p, q):
    if p and q are null: return true
    if p or q is null or p.val != q.val: return false
    return isSameTree(p.left, q.left) AND isSameTree(p.right, q.right)

Complexity Analysis: The time complexity of this approach is $O(M \times N)$, where $N$ is the number of nodes in root and $M$ is the number of nodes in subRoot. In the worst-case scenario (e.g., a skewed tree with identical values), for every node in root, we might traverse all nodes in subRoot.

Why it is suboptimal: While this approach passes the constraints of LeetCode 572 ($N, M \le 2000$), it performs redundant comparisons. We repeatedly traverse the same nodes in subRoot for different starting points in root. For significantly larger trees, this quadratic behavior would lead to performance issues.

Core Insight for Subtree of Another Tree

The key intuition is that a Binary Tree can be uniquely represented by a string if we utilize a specific traversal order (like Preorder) and explicitly record null pointers.

If we serialize the root tree into a string $S$ and the subRoot tree into a string $P$, the problem simplifies: Is $P$ a substring of $S$?

However, there are two crucial constraints we must enforce to make this work:

1. Null Markers: We must mark null children (e.g., using #) to distinguish between different structures that share the same values (e.g., a node with a left child vs. a node with a right child).
2. Value Delimiters: We must separate values to prevent partial matches. For example, without delimiters, a node with value 12 in the string could falsely match a subRoot node with value 2. We wrap values (e.g., ^12) to ensure we match full numbers.

Visual Description: Imagine the recursion traversing the tree in Preorder (Root, Left, Right). As it visits node 3, it writes ^3. It moves left to 4, writes ^4. It hits a leaf's left child (null), writes #. By the end, the tree structure is "frozen" into a linear sequence of characters. If subRoot's sequence appears contiguously inside root's sequence, the structures match.

Algorithm Strategy: Tree - Serialization and Deserialization

1. Define Serialization Logic: Create a helper function that performs a Preorder Traversal (DFS).
2. Handle Base Case: If a node is null, append a unique null marker (e.g., #) to the string.
3. Handle Recursive Step: If a node exists, append a delimiter followed by the node's value (e.g., ^ + val). Then, recursively serialize the left child, followed by the right child.
4. Serialize Both Trees: Generate string S for root and string T for subRoot.
5. String Matching: Check if T is a substring of S. If yes, return true; otherwise, false.

Execution Flow

Let's trace root = [3, 4, 5] and subRoot = [4].

1. Serialize subRoot ([4]):

   • Visit 4: Append ^4.
   • Recurse Left (null): Append #.
   • Recurse Right (null): Append #.
   • Result T: ^4##

2. Serialize root ([3, 4, 5]):

   • Visit 3: Append ^3.
   • Recurse Left (4):
     • Visit 4: Append ^4.
     • Left is null: Append #.
     • Right is null: Append #.
   • Recurse Right (5):
     • Visit 5: Append ^5.
     • Left is null: Append #.
     • Right is null: Append #.
   • Result S: ^3^4##^5##

3. Comparison:

   • Check if ^4## exists in ^3^4##^5##.
   • It does (starting at index 2).
   • Return true.

Proof of Correctness

A Preorder traversal that includes null markers provides a bijection between finite binary trees and their serialized strings. This means two trees are identical if and only if their serialized strings are identical. Consequently, if a tree $T$ is a subtree of $S$, the serialized representation of $T$ must appear as a contiguous substring within the serialized representation of $S$. The use of delimiters ensures that we do not match a suffix of a number (like 2 inside 12) or merge numbers incorrectly.

Reference Implementation

C++ Solution for LeetCode 572

cpp
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string fullTree = serialize(root);
        string subTree = serialize(subRoot);
        
        // Check if subTree string is a substring of fullTree string
        return fullTree.find(subTree) != string::npos;
    }

private:
    string serialize(TreeNode* node) {
        if (!node) {
            return "#"; // Null marker
        }
        // Preorder: Root, Left, Right
        // Using '^' as a delimiter to distinguish values like 12 vs 1, 2
        return "^" + to_string(node->val) + serialize(node->left) + serialize(node->right);
    }
};

Java Solution for LeetCode 572

java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String fullTree = serialize(root);
        String subTree = serialize(subRoot);
        
        return fullTree.contains(subTree);
    }
    
    private String serialize(TreeNode node) {
        if (node == null) {
            return "#"; // Null marker
        }
        
        StringBuilder sb = new StringBuilder();
        // Preorder: Root, Left, Right
        // Using '^' as a delimiter to separate values
        sb.append("^");
        sb.append(node.val);
        sb.append(serialize(node.left));
        sb.append(serialize(node.right));
        
        return sb.toString();
    }
}

Python Solution for LeetCode 572

python
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            if not node:
                return "#"
            # Preorder: Root, Left, Right
            # Using '^' to distinguish values (e.g. ^12 vs ^1)
            return f"^{node.val}" + serialize(node.left) + serialize(node.right)
        
        full_tree_str = serialize(root)
        sub_tree_str = serialize(subRoot)
        
        return sub_tree_str in full_tree_str