☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Subtree of Another Tree

Easy TUF ID 2408 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the roots of two binary trees, root and subRoot, return true if some node of root has a subtree that is identical to subRoot: same shape and same value at every position. The subtree of a node means that node together with all of its descendants, so a match must continue all the way down to the leaves. The whole of root counts as one of its own subtrees.

Constraints: root has 1 to 2000 nodes, subRoot has 1 to 1000, values are between -10^4 and 10^4. For completeness the code also defines the empty cases: an empty subRoot is a subtree of anything, and an empty root contains no non-empty subtree.

Example 1

root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
answer = true        // the node 4 in root has children 1 and 2 and nothing else

Example 2

root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
answer = false       // the 4 in root matches at the top, but its node 2 has an extra child 0

Approach 1: Brute force, try every node as a starting point

Intuition. If subRoot appears in root, its top must line up with some node of root. We don’t know which one, so try them all. For each node, run the “are these two trees identical” check: both empty, or both present with equal values and identical left and right subtrees. The answer is true if any node passes.

Algorithm.

  1. If subRoot is empty, return true. If root is empty, return false.
  2. Return isSame(root, subRoot), or else the same question for root.left, or else for root.right.
static boolean bruteForce(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;           // the empty tree is a subtree of every tree
    if (root == null) return false;
    return isSame(root, subRoot) || bruteForce(root.left, subRoot) || bruteForce(root.right, subRoot);
}

static boolean isSame(TreeNode p, TreeNode q) {
    if (p == null || q == null) return p == q;
    return p.val == q.val && isSame(p.left, q.left) && isSame(p.right, q.right);
}

Complexity. Time O(n · m) in the worst case, where n and m are the sizes of the two trees: every node of root can start an isSame call that walks almost all of subRoot before failing. That happens with many equal values, for example root a long chain of 1s and subRoot a chain of 1s ending in a 2. On typical inputs the comparison fails at the first node and it runs much faster. Space O(h) for the recursion, where h is the height of root.

For the given limits (2000 × 1000) this is fast enough and it is what most interviewers expect first. The follow-up is to make it linear.

Approach 2: Optimal, serialize both trees and search with KMP

Intuition. Turn the trees into sequences so the question becomes “does one sequence appear inside the other?”, which string matching answers in linear time.

The encoding is a preorder traversal that writes a marker for every missing child. Two facts make it work:

  1. A subtree is a contiguous block. Preorder writes a node, then everything in its left subtree, then everything in its right subtree. So the encoding of any node’s subtree appears as one unbroken block inside the encoding of root.
  2. The encoding identifies the tree exactly. With the null markers, a tree can be rebuilt from its encoding, so equal encodings mean identical trees. Without the markers that fails: [1, 2] (2 on the left) and [1, null, 2] (2 on the right) both give 1 2.

There is one more thing to check: could the pattern match a block that is not a whole subtree? No. Count open slots while reading an encoding: start with one slot; a value fills a slot and opens two (net +1), a marker fills one (net -1). An encoding of a tree is exactly a sequence where the count first reaches zero at its last token. If the pattern occurs starting at position p, the token at p is some node x, and the encoding of x’s subtree also starts at p. Both blocks end exactly where the slot count starting from p first reaches zero, so they are the same block, and x’s subtree is identical to subRoot.

The encoding uses long tokens: each value becomes itself, and the marker is Long.MAX_VALUE, which no int can equal. Matching whole tokens avoids the string pitfall where the text "12" contains "2" although the trees [12] and [2] have nothing in common. With strings you would need a separator before every value, as in ",12,#,#".

To find the pattern in the text we use KMP. A naive search restarts the pattern after every mismatch, which brings back O(n · m). KMP first computes lps[i], the length of the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch it falls back to lps[j - 1] instead of starting over, because those tokens are already known to match. The text pointer never moves backwards, so the search is linear.

Algorithm.

  1. Serialize root into text and subRoot into pattern (preorder, marker for each null).
  2. Build the lps table of pattern.
  3. Scan text with KMP; return true as soon as all of pattern is matched, otherwise false.
static final long NULL = Long.MAX_VALUE;        // no int value can equal this marker

static boolean optimal(TreeNode root, TreeNode subRoot) {
    List<Long> text = new ArrayList<>(), pattern = new ArrayList<>();
    serialize(root, text);
    serialize(subRoot, pattern);
    return kmpContains(toArray(text), toArray(pattern));
}

static void serialize(TreeNode node, List<Long> out) {
    if (node == null) {
        out.add(NULL);
        return;
    }
    out.add((long) node.val);
    serialize(node.left, out);
    serialize(node.right, out);
}

static long[] toArray(List<Long> list) {
    long[] a = new long[list.size()];
    for (int i = 0; i < a.length; i++) a[i] = list.get(i);
    return a;
}

static boolean kmpContains(long[] text, long[] pattern) {
    int m = pattern.length;
    int[] lps = new int[m];        // lps[i]: longest proper prefix of pattern[0..i] that is also a suffix of it
    int len = 0;
    for (int i = 1; i < m; i++) {
        while (len > 0 && pattern[i] != pattern[len]) len = lps[len - 1];
        if (pattern[i] == pattern[len]) len++;
        lps[i] = len;
    }
    int j = 0;                     // how many pattern tokens the current window matches
    for (long token : text) {
        while (j > 0 && token != pattern[j]) j = lps[j - 1];
        if (token == pattern[j]) j++;
        if (j == m) return true;
    }
    return false;
}

Dry run. Writing # for the marker:

tree encoding
subRoot [4, 1, 2] 4 1 # # 2 # #
Example 1 root 3 4 1 # # 2 # # 5 # #
Example 2 root 3 4 1 # # 2 0 # # # 5 # #

In Example 1 the pattern appears starting at the second token, which is the node 4. In Example 2 the attempt from the 4 matches 4 1 # # 2 and then sees 0 where the pattern needs #; KMP falls back, and no other position matches, so the answer is false.

Complexity. Time O(n + m): the two traversals, the lps table and the scan are each linear in the length of the encodings, which are 2n + 1 and 2m + 1 tokens. Space O(n + m) for the encodings, plus O(h) recursion while serializing.

Another linear-time option is to hash every subtree from its children’s hashes (a Merkle-style hash) and compare each node’s hash with the hash of subRoot, confirming candidate matches with isSame to rule out collisions. The serialization approach is exact without any such check.

Edge cases and pitfalls