Subtree of Another Tree

EasyTrees · DFS · Tree Matching🧩 Tree DFS LeetCode #572 ↗Updated Oct 30, 2026

Problem

Given two binary trees root and subRoot, return true if some node of root is the top of a subtree that is identical to subRoot — same shape and same values, all the way down to the leaves. A tree also counts as a subtree of itself.

Inputroot = [3,4,5,1,2], subRoot = [4,1,2]Outputtrue

Inputroot = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Outputfalse

Inputroot = [1,1], subRoot = [1]Outputtrue

1 ≤ nodes in root ≤ 2000 · 1 ≤ nodes in subRoot ≤ 1000 · -10⁴ ≤ Node.val ≤ 10⁴

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A match must be a whole subtree, so it must have the same height as subRoot. Nodes of equal height can never be ancestors of each other, so their subtrees are disjoint — comparing only at those nodes touches every node at most once.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceTry Every Node as a Start

Time O(n · m)Space O(h)

Visit each node of root and run a full same-tree comparison between that node and subRoot. If any comparison succeeds we are done. A comparison can cost up to m steps and there are n starting points.

Java

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    if (same(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean same(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
}

The natural first answer and fine for these limits, but quadratic in the worst case.

BetterSerialize + KMP String Search

Time O(n + m)Space O(n + m)

Encode both trees in pre-order with a # for every null child and a comma before every token. With these markers a subtree's encoding is a contiguous block of the big encoding, and a block equal to subRoot's encoding must be a matching subtree. KMP finds the block in linear time.

Java

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    StringBuilder text = new StringBuilder(), pat = new StringBuilder();
    encode(root, text);
    encode(subRoot, pat);
    return kmpContains(text.toString(), pat.toString());
}
private void encode(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append(",#");
        return;
    }
    sb.append(',').append(node.val); // leading comma: ",2" never matches inside ",12"
    encode(node.left, sb);
    encode(node.right, sb);
}
private boolean kmpContains(String text, String pat) {
    int[] lps = new int[pat.length()]; // longest proper prefix that is also a suffix
    for (int i = 1, len = 0; i < pat.length(); ) {
        if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
        else if (len > 0) len = lps[len - 1];
        else lps[i++] = 0;
    }
    for (int i = 0, j = 0; i < text.length(); ) {
        if (text.charAt(i) == pat.charAt(j)) {
            i++;
            j++;
            if (j == pat.length()) return true;
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return false;
}

Linear time, but needs two strings and the prefix table in memory.

OptimalHeight-Filtered Comparison

Time O(n + m)Space O(h)

Compute the height of subRoot once. A post-order walk returns each node's height; only when it equals the target height do we run a same-tree check. Those candidate subtrees are pairwise disjoint, so all checks together cost at most n steps, and nothing beyond the recursion stack is stored.

Java

private int target;
private TreeNode pattern;
private boolean found;

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    pattern = subRoot;
    target = height(subRoot);
    found = false;
    walk(root);
    return found;
}
private int walk(TreeNode node) { // returns height, checks candidates on the way up
    if (node == null || found) return 0;
    int h = 1 + Math.max(walk(node.left), walk(node.right));
    if (h == target && !found && same(node, pattern)) found = true;
    return h;
}
private int height(TreeNode node) {
    return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
}
private boolean same(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
}

Linear time with only stack space — no hashing, no strings.

Pro tip

Say why it's linear: equal-height nodes can't be ancestor/descendant, so the compared subtrees never overlap.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Node as a Start	`O(n · m)`	`O(h)`
Better	Serialize + KMP String Search	`O(n + m)`	`O(n + m)`
Optimal	Height-Filtered Comparison	`O(n + m)`	`O(h)`

Common pitfalls

Accepting a node whose subtree starts like subRoot but has extra descendants — leaves must line up too.
Serializing without null markers or separators — gives false matches like 2 inside 12.
Returning after the first node with a matching value; another node with that value may still match.

Interview tips

Start with “check every node with Same Tree” and state O(n·m) honestly.
Offer serialization + KMP (or rolling hash) as the classic linear upgrade.
Close with the height filter — linear time, O(h) space, and easy to prove.

Pattern

Tree matching via DFS + same-tree check → find whether a tree pattern appears as a full subtree; upgrade with serialization or a size/height filter.

My notes saved in this browser