Subtree of Another Tree Solution Explained – Step-by-Step

Data Structures / Tree

Subtree of Another Tree

Easy

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.

A subtree of a binary tree is a tree that consists of a node in the tree and all of its descendants. The tree itself is also considered a subtree.

Example

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Explanation: The subtree rooted at node 4 matches subRoot.

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

Explanation

This problem combines two concepts: tree traversal and tree comparison. We need to check if any subtree of the main tree matches the target subtree exactly.

The approach uses two recursive functions:

isSubtree(root, subRoot): Traverses every node in the main tree and checks if the subtree starting at that node matches subRoot
isSameTree(p, q): Helper function that checks if two trees are identical (same structure and values)

For each node in the main tree:

If the subtree starting at this node is identical to subRoot, return true
Otherwise, recursively check the left and right subtrees
If subRoot is null, it's always a subtree (empty tree is subtree of any tree)
If root is null but subRoot isn't, return false

Idea Map

isSubtree(root, subRoot)

Is subRoot null?

Yes → return true

No → continue

Is root null?

Yes → return false

No → continue

Call isSameTree(root, subRoot)

return isSameTree(...)
|| isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot)

End

Complexity Analysis

Time Complexity

O(m × n) - In worst case, we check isSameTree (O(n)) for each of the m nodes in root.

Space Complexity

O(m + n) - Recursion stack depth is the maximum height of both trees combined.

Code


def isSubtree(root, subRoot):
Main function: checks if subRoot is a subtree of root.
    if not subRoot:
Edge case: empty tree is a subtree of any tree.
        return True
Return True since an empty tree can always be found.
    if not root:
If root is empty but subRoot isn't, no match possible.
        return False
Return False - can't find a subtree in an empty tree.
    if isSameTree(root, subRoot):
Check if trees starting at current nodes are identical.
        return True
Found a match! Return True.
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
Recurse on left OR right subtree - only need one match.


def isSameTree(p, q):
Helper function: checks if two trees are identical.
    if not p and not q:
Both null means both subtrees are empty - identical.
        return True
Return True for two empty trees.
    if not p or not q:
Only one is null - trees differ in structure.
        return False
Return False - structural mismatch.
    if p.val != q.val:
Check if current nodes have different values.
        return False
Return False - value mismatch.
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Recurse on both children - both must match.


public boolean isSubtree(TreeNode root, TreeNode subRoot) {
Main method: checks if subRoot is a subtree of root.
    if (subRoot == null) {
Edge case: empty tree is a subtree of any tree.
        return true;
Return true since an empty tree can always be found.
    }
End of first if block.
    if (root == null) {
If root is empty but subRoot isn't, no match possible.
        return false;
Return false - can't find a subtree in an empty tree.
    }
End of second if block.
    if (isSameTree(root, subRoot)) {
Check if trees starting at current nodes are identical.
        return true;
Found a match! Return true.
    }
End of third if block.
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
Recurse on left OR right subtree - only need one match.
}
End of isSubtree method.

private boolean isSameTree(TreeNode p, TreeNode q) {
Helper method: checks if two trees are identical.
    if (p == null && q == null) return true;
Both null means both subtrees are empty - identical.
    if (p == null || q == null) return false;
Only one is null - trees differ in structure.
    if (p.val != q.val) return false;
Check if current nodes have different values.
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
Recurse on both children - both must match.
}
End of isSameTree method.


bool isSubtree(TreeNode* root, TreeNode* subRoot) {
Main function: checks if subRoot is a subtree of root.
    if (subRoot == nullptr) {
Edge case: empty tree is a subtree of any tree.
        return true;
Return true since an empty tree can always be found.
    }
End of first if block.
    if (root == nullptr) {
If root is empty but subRoot isn't, no match possible.
        return false;
Return false - can't find a subtree in an empty tree.
    }
End of second if block.
    if (isSameTree(root, subRoot)) {
Check if trees starting at current nodes are identical.
        return true;
Found a match! Return true.
    }
End of third if block.
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
Recurse on left OR right subtree - only need one match.
}
End of isSubtree function.

bool isSameTree(TreeNode* p, TreeNode* q) {
Helper function: checks if two trees are identical.
    if (!p && !q) return true;
Both nullptr means both subtrees are empty - identical.
    if (!p || !q) return false;
Only one is nullptr - trees differ in structure.
    if (p->val != q->val) return false;
Check if current nodes have different values.
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
Recurse on both children - both must match.
}
End of isSameTree function.

Edge Cases & Common Mistakes

⚠️

Check subRoot first

Always check if subRoot is null before checking if root is null. An empty subRoot is a subtree of any tree, including an empty root.

💡

Partial match isn't enough

A subtree must match completely. If subRoot has a node where root has null, it's not a match. The isSameTree helper ensures exact structural and value match.

✓

Short-circuit with OR

Using `||` means we stop as soon as we find a match. If the left subtree contains the match, we never check the right.

🔄

Alternative: Tree Serialization

Convert both trees to strings and use string matching (KMP). This can be O(m + n) but requires careful handling of delimiters to avoid false matches.

Deep Dive: Tree Matching

Tree matching is a fundamental pattern recognition problem. The techniques here—combining traversal with comparison—apply to many problems like finding duplicate subtrees, pattern matching in trees, and tree isomorphism.

Learn more about tree matching →

device_hub

Disclaimer: This problem is for educational purposes. Practice the 'Subtree of Another Tree' problem on LeetCode.

AlgoExplained.dev