51.Subtree of Another Tree

EasyBlind 75Trees · 6/15

Problem

Given the roots of two binary trees root and subRoot, return true if there is a node in root whose subtree is identical to subRoot (same structure and same values), and false otherwise.

A subtree of a node consists of that node and all of its descendants — you cannot cut off part of it. The whole tree root counts as a subtree of itself.

Examples

Input:  root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Explanation: The subtree rooted at node 4 is exactly 4 -> (1, 2).

Input:  root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Explanation: Node 4's subtree also contains 0 under node 2, so it is not identical.

Constraints

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

💡 Key Insight

A subtree match must start at some node of root and then be a Same Tree check from there. Trying every start node costs O(m · n). To do better, serialize both trees with pre-order traversal and explicit null markers: a subtree of root becomes a contiguous substring of root's serialization, so the problem turns into string matching, which KMP solves in linear time.

Brute Force (Same Tree at Every Node)

TimeO(m · n)SpaceO(h)

Intuition

Visit every node of root. Treat it as a candidate starting point and run the Same Tree check against subRoot. If any candidate matches, return true.

Algorithm

If root is null, return false (subRoot is non-empty).
If sameTree(root, subRoot), return true.
Otherwise return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).
sameTree(a, b): both null -> true; one null or values differ -> false; else recurse on both children.

Dry Run

flowchart TD
    R3["3"] --> R4["4"]
    R3 --> R5["5"]
    R4 --> R1["1"]
    R4 --> R2["2"]
    S["candidate 3: sameTree fails (3 vs 4)"] --> T["candidate 4: sameTree(4, subRoot)"]
    T --> U["1 = 1, 2 = 2, all nulls match -> true"]

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (sameTree(root, subRoot)) {
            return true; // match starting at this node
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean sameTree(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null || a.val != b.val) {
            return false;
        }
        return sameTree(a.left, b.left) && sameTree(a.right, b.right);
    }
}

Complexity

Time: O(m · n) — up to m start nodes, each comparison up to n nodes (m = |root|, n = |subRoot|).
Space: O(h) — recursion depth of the taller tree.

Serialization + KMPOptimal

TimeO(m + n)SpaceO(m + n)

Intuition

Serialize each tree in pre-order, writing a separator before every token and # for null: [4,1,2] becomes ,4,1,#,#,2,#,#. Because the null markers pin down the structure, the serialization of any node's subtree appears as one contiguous block inside the serialization of root, and any match of the pattern must correspond to a full subtree. The leading comma ensures token boundaries line up, so ,2 cannot match the tail of ,12. Then run KMP to search for the pattern in O(m + n).

Algorithm

text = serialize(root), pattern = serialize(subRoot), both using ",val" for nodes and ",#" for null.
Build the KMP failure array lps for pattern.
Scan text with KMP; if the full pattern is matched, return true.
Return false.

Visualization

root    = [3,4,5,1,2]  -> text    = ",3,4,1,#,#,2,#,#,5,#,#"
subRoot = [4,1,2]      -> pattern = ",4,1,#,#,2,#,#"

text:    ,3 ,4,1,#,#,2,#,#  ,5,#,#
            ^^^^^^^^^^^^^^  found -> true

Second example: node 2 has child 0, so text contains
",4,1,#,#,2,0,#,#,#" -- after ",2" comes ",0" instead of ",#" -> no match

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        StringBuilder t = new StringBuilder();
        StringBuilder p = new StringBuilder();
        serialize(root, t);
        serialize(subRoot, p);
        return kmpContains(t.toString(), p.toString());
    }

    // separator before every token keeps value boundaries aligned
    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(",#");
            return;
        }
        sb.append(',').append(node.val);
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    private boolean kmpContains(String text, String pattern) {
        int[] lps = buildLps(pattern);
        int j = 0; // characters of pattern matched so far
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = lps[j - 1]; // fall back without moving i
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                return true;
            }
        }
        return false;
    }

    // lps[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix
    private int[] buildLps(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) {
                len = lps[len - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
            }
            lps[i] = len;
        }
        return lps;
    }
}

Complexity

Time: O(m + n) — two linear serializations plus a linear KMP scan (string lengths are proportional to node counts since values have at most 6 characters).
Space: O(m + n) — the two strings and the lps array.

Complexity Comparison

Approach	Time	Space
Brute Force (Same Tree at Every Node)	O(m · n)	O(h)
Serialization + KMP	O(m + n)	O(m + n)

Common Pitfalls

Serializing without null markers — different shapes can produce the same value sequence, and the second example would wrongly return true.
Omitting the leading separator: without it, pattern "2,#,#" would match inside "12,#,#".
Only checking whether subRoot's values appear somewhere — the match must include all descendants, so extra children (like 0 in example 2) break it.
Using String.contains / indexOf and calling it linear — Java's implementation is a naive search with O(m · n) worst case; KMP guarantees O(m + n).