Subtree of Another Tree

Ishaan S Published 24 Oct, 2026

You are given the roots of two binary trees, root and subRoot. Return true if some node of root is the top of a subtree that is identical to subRoot, and false otherwise.

A subtree of a node consists of that node and all of its descendants, so a match must agree on every value and every child position all the way down to the leaves; root itself also counts as one of its own subtrees.

Both trees are written in level order with null for missing children.

Example 1

Input: root = [8,6,9,2,7], subRoot = [6,2,7] Output: true Why: The subtree rooted at the 6 has children 2 and 7, exactly like subRoot.

Example 2

Input: root = [8,6,9,2,7,null,null,null,null,5], subRoot = [6,2,7] Output: false Why: The 6 in root also has the 5 below its 7, so its subtree is not an exact copy of subRoot.

Example 3

Input: root = [3,1,4], subRoot = [1] Output: true Why: The leaf 1 (left child of the root) is a single-node subtree equal to subRoot.

Constraints

1 <= nodes in root <= 2000
1 <= nodes in subRoot <= 1000
-10⁴ <= Node.val <= 10⁴

Pattern Path · Trees: DFS · problem 86 of 169

Split the problem in two: (a) are two given trees exactly the same? (b) which nodes of root should you try as the top of a match?

Two trees are the same when both are empty, or both roots have equal values and their left subtrees are the same and their right subtrees are the same.

Visit every node of root; if the tree starting there is the same as subRoot, return true. Otherwise search the left and right subtrees.

Target: O(m · n) worst case time, O(h) recursion depth extra space.

Start simple

This problem's natural solution already tries each node as a candidate: O(m · n) time for m and n nodes. A more naive variant serializes every subtree of root separately and compares strings, which costs even more time and memory.

The key idea

Break the task into two recursive questions.

Same tree? same(a, b) is true when both are empty, or when both exist, have equal values, and same(a.left, b.left) and same(a.right, b.right) hold. It stops at the first difference.

Where could it start? A matching subtree must begin at some node of root. So isSubtree(node) is true if same(node, subRoot), or if the match is somewhere in the left or right subtree. An empty node cannot contain a non-empty subRoot.

Because same compares down to the leaves, a node whose subtree merely contains the pattern plus extra children is correctly rejected.

In the worst case same runs for up to n nodes at each of the m nodes of root, so the time is O(m · n), but it usually fails within a few steps. For a guaranteed linear bound you can serialize both trees with explicit null markers and run a string search (KMP), or compare hashes of subtrees.

Complexity

Time: O(m · n) worst case
Space: O(h) recursion depth

Python

class Solution:
    def isSubtree(self, root, subRoot):
        def same(a, b):
            if a is None or b is None:
                return a is b
            return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)

        if root is None:
            return False
        if same(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

JavaScript

var isSubtree = function(root, subRoot) {
  const same = (a, b) => {
    if (!a || !b) return a === b;
    return a.val === b.val && same(a.left, b.left) && same(a.right, b.right);
  };
  if (!root) return false;
  if (same(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

What the interviewer is checking

It tests whether you can compose two recursive functions cleanly, and whether you can discuss the worst case and a linear-time improvement via serialization or hashing.

Mistakes to avoid

Accepting a node whose subtree contains subRoot plus extra descendants (comparing only the top part).
Serializing without null markers or value separators, so different trees produce the same string (e.g. 12 vs 1,2).
Only trying to match at nodes whose value equals subRoot's root but forgetting to keep searching after a failed match.

Follow-ups to expect

Can you make it linear? (Serialize with nulls, then KMP search.)
What if the trees are huge and compared often? (Merkle-style subtree hashes.)
Count how many times subRoot occurs. (Keep counting instead of returning early.)

In real software

Finding a repeated component inside a larger structure, such as a code fragment in an abstract syntax tree for clone detection, or an element pattern in a DOM, is this problem at scale.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return false;
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>(List.of(root));
        for (int i = 1; i < a.length; i += 2) {
            TreeNode n = q.poll();
            if (a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            if (i + 1 < a.length && a[i + 1] != null) { n.right = new TreeNode(a[i + 1]); q.add(n.right); }
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{8, 6, 9, 2, 7});
        TreeNode subRoot = build(new Integer[]{6, 2, 7});
        System.out.println(new Solution().isSubtree(root, subRoot)); // true
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        return false;
    }
};

// Builds a tree from a level-order array (INT_MIN = missing child).
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == INT_MIN) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    for (size_t i = 1; i < a.size(); i += 2) {
        TreeNode* n = q.front(); q.pop();
        if (a[i] != INT_MIN) { n->left = new TreeNode(a[i]); q.push(n->left); }
        if (i + 1 < a.size() && a[i + 1] != INT_MIN) { n->right = new TreeNode(a[i + 1]); q.push(n->right); }
    }
    return root;
}

int main() {
    TreeNode* root = build({8, 6, 9, 2, 7});
    TreeNode* subRoot = build({6, 2, 7});
    cout << boolalpha << Solution().isSubtree(root, subRoot) << endl;  // true
}

Topics #086 #t-tree-dfs DFS Easy Practice Recursion Tree