Subtree of Another Tree

The problem

You are given the roots of two binary trees, root and subRoot. Return true if root contains a subtree that is exactly the same as subRoot, and false if not.

A subtree is a node plus everything below it. So the copy must have the same values and the same shape, all the way down to the leaves. A tree also counts as a subtree of itself.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [5, 9, 9, 1, null, 1, 4], subRoot = [9, 1, 4]

Output: true

The right 9 of root has children 1 and 4, exactly like subRoot. The left 9 has only the 1, so it is not a copy.

Example 2

Input: root = [2, 1, 3], subRoot = [2, 1]

Output: false

The tree under 2 also holds 3. A subtree must take everything below its node, so it is [2, 1, 3], not [2, 1].

Example 3

Input: root = [4, 4], subRoot = [4]

Output: true

The leaf 4 on its own is a subtree, and it equals subRoot.

Constraints

• root has 1 to 2,000 nodes. Call this m.
• subRoot has 1 to 1,000 nodes. Call this n.
• -10,000 ≤ Node.val ≤ 10,000

Clarifying questions

Must the copy reach down to the leaves?

Yes. A subtree takes a node and everything below it. A match that stops early, with more nodes under it in root, does not count.

Can values repeat?

Yes. That is why we cannot just find the value of subRoot once. Several nodes may start a near copy.

Can either tree be empty?

No. Both have at least one node, so there is always something to compare.

Does the whole tree count as a subtree of itself?

Yes. If root and subRoot are the same, the answer is true.

Spot the pattern

The question “is the tree under this node the same as subRoot?” is the Same Tree problem. We ask it at every node, which is a tree traversal. The faster way comes from turning both trees into lists and searching for one list inside the other, which is string matching.

Solutions

Brute forceO(m × n)OptimalO(m + n)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(m × n)

The idea

Visit every node of root. At each one, ask a helper same() whether the tree that starts there equals subRoot. same() walks both trees together and stops at the first difference: a different value, or a node on one side where the other side has an empty spot.

If any start gives true, the answer is true. This is easy to write and easy to trust. But in the worst case, each of the m starts walks almost all n nodes of subRoot.

Walkthrough

calls to same() so far

0

1. def is_subtree(root, sub_root):
2. if root is None:
3. return False
4. if same(root, sub_root):
5. return True
6. return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

root is on the left, subRoot on the right. Try every node of root as the place where a copy of subRoot might start.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: at every node of root, check whether the tree that
    // starts there is the same as subRoot. m starts, each up to n checks.
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // No nodes left, so no place for subRoot to start.
        if (root == null) return false;
        // Maybe the copy starts right here.
        if (isSame(root, subRoot)) return true;
        // If not, it can only start somewhere below.
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSame(TreeNode firstTree, TreeNode secondTree) {
        // Same shape and same values, checked pair by pair.
        if (firstTree == null && secondTree == null) return true;
        if (firstTree == null || secondTree == null || firstTree.val != secondTree.val)
            return false;
        return isSame(firstTree.left, secondTree.left) && isSame(firstTree.right, secondTree.right);
    }
}

Big O

Time O(m × n)Space O(m + n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line calls same(), and it runs once for every node of root. same() is a recursion too, so we count its calls. Each call does a fixed job: a few checks and at most two more calls. So each call of same() counts as 1 step.

   1. def is_subtree(root, sub_root):
   2. if root is None:
   3. return False
   4. if same(root, sub_root):
   5. return True
   6. return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

2. 2 Count the runs on Example 1

   Example 1 tries 4 starts before it finds the copy. Each row shows how many calls same() made at that start. The left 9 gets far before it fails, which is what makes this approach slow.

   1 + 5 + 1 + 7 = 14 calls to same().

   start at	5	9 (left)	1	9 (right)
   same() calls	1	5	1	7
   result	no	no	no	yes

   total

   1 + 5 + 1 + 7 = 14 calls

3. 3 Write the count for any n

   There are m starts. At one start, same() can walk all n nodes of subRoot and its n + 1 empty spots before it fails, so up to 2n + 1 calls. The worst case is when almost every start nearly matches, for example a root of all 1s and a subRoot of all 1s with one 2 at the bottom.

   m × (2n + 1) = 2mn + m calls

   Check it with Example 1: m is 6 and n is 3, so this bound is 6 × 7 = 42. The real run used 14, because most starts failed fast. Big O counts the worst case.

4. 4 Keep only the part that grows fastest

   • Drop the + m. Next to 2mn it does not matter.
   • Drop the 2. Doubling every count does not change the growth.

   What is left is m × n. Both trees can grow on their own, so both letters stay.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   The code makes no list or map. The memory is the call stack: calls that started and have not returned. is_subtree can be up to the height of root deep, and inside it same() adds up to the height of subRoot. In the worst case both trees are chains, so the space is O(m + n).

   call stack of is_subtreecall stack of same

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 2,000 nodes, that is 2,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Optimal O(m + n)

The idea

Write each tree as a list in pre-order: the node, then its left subtree, then its right subtree. Write # for every empty spot. The # marks fix the shape, so two trees are equal exactly when their lists are equal.

A subtree is also one unbroken run of the pre-order list: pre-order writes a node and then everything below it, before moving on. So subRoot is a subtree of root exactly when the list of subRoot appears as one block inside the list of root.

Now it is a search for a pattern inside a text. KMP (Knuth-Morris-Pratt) does that without ever moving back in the text. It first builds a table fallback for the pattern: for each position, the length of the longest start of the pattern that also ends there. After a mismatch, fallback says how much of the match can still be kept.

Why it never misses the answer: the lists match exactly when the trees match, and KMP finds every place where the pattern appears in the text.

Walkthrough

text (root)

509112#3#4#59617#8#9410#11#12

1. text = preorder(root) # "#" for each empty spot
2. pattern = preorder(sub_root)
3. fallback = fallback_table(pattern)
4. matched = 0
5. for value in text:
6. while matched > 0 and value != pattern[matched]:
7. matched = fallback[matched - 1]
8. if value == pattern[matched]:
9. matched += 1
10. if matched == len(pattern):
11. return True
12. return False

Write root in pre-order: node, then left subtree, then right subtree. Every empty spot becomes #. That gives 13 items.

← BackStep →Play1 / 17

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Pre-order lists with a marker for every empty spot, then KMP search.
    // Building the lists is m + n steps, and KMP never moves backwards.
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<Integer> text = new ArrayList<>(), pattern = new ArrayList<>();
        walk(root, text);
        walk(subRoot, pattern);
        // fallback[j]: the longest start of pattern that also ends at pattern[j].
        // After a mismatch, KMP falls back to it instead of starting over.
        int[] fallback = new int[pattern.size()];
        for (int j = 1, prefixLength = 0; j < pattern.size(); j++) {
            while (prefixLength > 0 && !Objects.equals(pattern.get(j), pattern.get(prefixLength)))
                prefixLength = fallback[prefixLength - 1];
            if (Objects.equals(pattern.get(j), pattern.get(prefixLength))) prefixLength++;
            fallback[j] = prefixLength;
        }
        int matched = 0;
        for (Integer value : text) {
            // On a mismatch, keep the part of the match that can still grow.
            while (matched > 0 && !Objects.equals(value, pattern.get(matched)))
                matched = fallback[matched - 1];
            if (Objects.equals(value, pattern.get(matched))) matched++;
            // The whole pattern matched: a full copy of subRoot.
            if (matched == pattern.size()) return true;
        }
        return false;
    }

    private void walk(TreeNode node, List<Integer> values) {
        // The null markers fix the shape, so equal lists mean equal trees.
        if (node == null) {
            values.add(null);
            return;
        }
        values.add(node.val);
        walk(node.left, values);
        walk(node.right, values);
    }
}

Big O

Time O(m + n)Space O(m + n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are four parts: two pre-order walks, the fallback table and the scan. Each pre-order call writes one item. Each run of the scan reads one item, and each run of the inner while steps matched back once. Each of these is a fixed job, so each counts as 1 step.

   1. text = preorder(root) # "#" for each empty spot
   2. pattern = preorder(sub_root)
   3. fallback = fallback_table(pattern)
   4. matched = 0
   5. for value in text:
   6. while matched > 0 and value != pattern[matched]:
   7. matched = fallback[matched - 1]
   8. if value == pattern[matched]:
   9. matched += 1
   10. if matched == len(pattern):
   11. return True
   12. return False

2. 2 Count the runs on Example 1

   The pre-order of root writes 13 items, one call each. The pre-order of subRoot writes 7. The fallback loop runs once for each item of the pattern after the first: 6 runs. The scan reads 13 items and falls back once, at the # where the pattern wanted 4.

   13 + 7 + 6 + 14 = 40 steps.

   part	preorder(root)	preorder(sub)	lps table	scan text	total
   steps	13	7	6	14	40

3. 3 Write the count for any n

   A tree with m nodes has m + 1 empty spots, so its list has 2m + 1 items. The scan reads each text item once. The while can only step matched back as many times as matched went up, and matched goes up at most once per item. The fallback loop works the same way on the pattern. So:

   (2m + 1) + (2n + 1) + 2(2n + 1) + 2(2m + 1) = 6m + 6n + 6

   Check it with Example 1: this bound is 6 × 6 + 6 × 3 + 6 = 60. The real run used 40, because most items did not fall back.

4. 4 Keep only the part that grows fastest

   • Drop the + 6. A fixed amount does not change the growth.
   • Drop the 6s. When m and n double, 6m + 6n doubles too.

   What is left is m + n.

   So the time is O(m + n).

5. S Space: count the extra memory the same way

   The two lists hold 2m + 1 and 2n + 1 items, and fallback holds 2n + 1. The pre-order walks also use a call stack as deep as each tree. All of it grows with m + n, so the space is O(m + n).

   text (2m + 1 items)pattern (2n + 1 items)fallback (2n + 1 items)call stack

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 2,000 nodes, that is 2,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Leaving out the empty markers

Without #, the pre-order of [2, 1] and of [2, null, 1] are both 2, 1. Different shapes give the same list, and the search reports false copies. Every empty spot must be written down.

Tested at the limits

2,000 random pairs of trees: a root of 1 to 10 nodes, and a subRoot that is often cut out of it, sometimes with one value changed. The brute force and the optimal solution gave the same answer every time.

Largest inputs	Result
2,000 nodes in root and 1,000 in subRoot (the most allowed), both one long line, every value 0 except the last node of subRoot. Optimal.	0.001 s, and about 0.4 MB of extra memory: the two lists of values and the calls that wait during the walk, which is the O(m + n) space.
The same two lines. Brute force.	0.2 s. At each of the 2,000 starting nodes it compares up to 1,000 nodes before the last one differs, about 1.5 million steps.