Subtree of Another Tree

easy
TreesTreeBinary TreeDepth-First Search

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, and false otherwise. A subtree of a binary tree is a tree that consists of a node in the tree and all of its descendants. The tree could also be considered a subtree of itself.

Examples

Example 1

  • Input: root = [3,4,5,1,2], subRoot = [4,1,2]
  • Output: true
  • Explanation: The left subtree of root is identical to subRoot.

Example 2

  • Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
  • Output: false
  • Explanation: The subtree rooted at node 4 has an extra child node 0, so it does not match subRoot.

Constraints

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive Tree Comparison

Intuition

The straightforward approach is to visit every node in the main tree and check whether the subtree rooted at that node is identical to subRoot. We reuse the "same tree" check as a helper. For each node in root, if it matches subRoot exactly (same structure and values), we return true. Otherwise, we recursively check the left and right subtrees. This approach is simple to implement and builds on the same-tree problem.

Algorithm

  1. If root is null, return false (no subtree can match).
  2. If the tree rooted at root is the same as subRoot (using the isSameTree helper), return true.
  3. Recursively check if subRoot is a subtree of root.left OR root.right.
  4. The isSameTree helper checks: both null returns true, one null returns false, different values returns false, and recursively compares left and right children.
TimeO(m * n) where m is the size of root and n is the size of subRootSpaceO(m) for the recursion stack in the worst case

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr) return false;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }

private:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
Java 21
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
Python 3.12
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def is_same(p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return is_same(p.left, q.left) and is_same(p.right, q.right)

    if not root:
        return False
    if is_same(root, subRoot):
        return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
Go 1.26
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }
    if isSameTree(root, subRoot) {
        return true
    }
    return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
Approach 2

String Serialization Matching

Intuition

Instead of comparing trees node by node, we can serialize both trees into strings and check if the serialized subRoot is a substring of the serialized root. We use a preorder traversal with special markers for null nodes and delimiters between node values to avoid false matches (e.g., "12" matching "1" and "2"). If the serialized subRoot appears as a substring of the serialized root, then subRoot is a subtree. This reduces the problem to substring matching.

Algorithm

  1. Serialize root into a string using preorder traversal with null markers and delimiters.
  2. Serialize subRoot into a string using the same method.
  3. Check if the serialized subRoot is a substring of the serialized root.
  4. Use delimiters (e.g., commas) and a special null marker to prevent false matches.
TimeO(m + n) with efficient substring matching, or O(m * n) with naive matchingSpaceO(m + n) for the serialized strings

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string rootStr = serialize(root);
        string subStr = serialize(subRoot);
        return rootStr.find(subStr) != string::npos;
    }

private:
    string serialize(TreeNode* node) {
        if (node == nullptr) return ",#";
        return "," + to_string(node->val) + serialize(node->left) + serialize(node->right);
    }
};
Java 21
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String rootStr = serialize(root);
        String subStr = serialize(subRoot);
        return rootStr.contains(subStr);
    }

    private String serialize(TreeNode node) {
        if (node == null) return ",#";
        return "," + node.val + serialize(node.left) + serialize(node.right);
    }
}
Python 3.12
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def serialize(node):
        if not node:
            return ",#"
        return "," + str(node.val) + serialize(node.left) + serialize(node.right)

    return serialize(subRoot) in serialize(root)
Go 1.26
import "strings"

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    rootStr := serialize(root)
    subStr := serialize(subRoot)
    return strings.Contains(rootStr, subStr)
}

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

Frequently asked questions

What is the optimal time complexity of Subtree of Another Tree?

The most efficient approach in this guide ("String Serialization Matching") runs in O(m + n) with efficient substring matching, or O(m * n) with naive matching time and uses O(m + n) for the serialized strings extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Subtree of Another Tree use?

Subtree of Another Tree is a easy-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Subtree of Another Tree be solved without extra space?

The most space-efficient approach in this guide uses O(m + n) for the serialized strings extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m) for the recursion stack in the worst case, while the optimized version uses O(m + n) for the serialized strings.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Same Tree

Original problem: leetcode.com

Loading editor...
Input
root=
[3,4,5,1,2]
subRoot=
[4,1,2]
Expected Output
true