Subtree of Another Tree

Given the roots of two binary trees, root and subRoot, return true if some node of root starts a subtree with exactly the same shape and values as subRoot. That subtree must be the node plus all of its descendants, so it has to end where subRoot ends. This is LeetCode 572.

Limits: root has 1 to 2000 nodes, subRoot has 1 to 1000 nodes, and every value is between -104 and 104.

Example 1
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true
Explanation: the left child of 3 holds the tree 4 with children 1 and 2.
Example 2
Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false
Explanation: the 2 under node 4 has a left child 0, while the 2 in subRoot is a leaf.
Example 3
Input: root = [1, 1], subRoot = [1]
Output: true
Explanation: the root does not match because it has a child, but the lone leaf 1 below it does.

How to Think About It

Step 1: Name the candidates

A subtree is fixed by its top node: pick a node of root, and its subtree is that node with everything below it. So there are exactly as many candidates as root has nodes, at most 2000.

Step 2: Test one candidate with Same Tree

A candidate matches when it and subRoot are identical trees. That is the check from Same Tree: equal values at the two tops, then the left children compared as trees, then the right children.

Step 3: Try every node with a traversal

The answer is true if the tree rooted at root matches, or if a match exists somewhere in the left subtree, or in the right subtree. That sentence is already the recursion. An empty tree has no candidates, so it returns false.

Step 4: Why a value match is not the end

Equal top values only make a node worth checking. In Example 3 the root 1 equals the top of subRoot, yet the root has a child and subRoot does not. The search must go on and find the leaf below it.

Step 5: Why the check needs the ends to agree

Same Tree fails when one side has a child and the other has null. That is what rules out Example 2: the shape 4, 1, 2 is there, but the extra 0 under the 2 makes it a different subtree.

Walkthrough

Example 2, in the order the recursion visits the nodes of root.

Candidate topComparison with subRootResult
33 vs 4values differ: false
44 vs 4, then 1 vs 1 (both leaves), then 2 vs 22 has left child 0, subRoot's 2 has none: false
11 vs 4values differ: false
22 vs 4values differ: false
00 vs 4values differ: false
55 vs 4values differ: false

No candidate matches, so the answer is false. In Example 1 the second row succeeds and the search stops there.

Java Solution

isSubtree walks the nodes of root in preorder and asks isSameTree whether the tree starting at each one is a copy of subRoot.

  • The base case: when root is null there is no node left to start from, so the answer is false. subRoot always has at least one node, so an empty spot never matches it.
  • Three chances: the || chain tries the current node first, then the left subtree, then the right. It stops at the first true, so Example 1 never visits node 5.
  • The null check in isSameTree: a == b is true only when both are null. That is how an extra child on either side, like the 0 in Example 2, ends a match.
  • Negative values: values are compared with == on int, so -104 and 104 need no special handling. [-10000, 10000] contains [10000].

A common mistake is to stop at the first node whose value equals subRoot.val and return that one comparison. In Example 3 the root 1 fails the comparison, the search never reaches the leaf below, and the method returns false instead of true.

Java
public class SubtreeOfAnotherTree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false; // ran out of places where subRoot could start
        }
        return isSameTree(root, subRoot)
                || isSubtree(root.left, subRoot)
                || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode a, TreeNode b) {
        if (a == null || b == null) {
            return a == b; // equal only if both are missing
        }
        return a.val == b.val && isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
    }
}

Complexity

  • Time: O(m × n), where m and n are the node counts of root and subRoot. Each of the m nodes starts one comparison, and a comparison can walk up to n nodes before it fails. Two chains of equal values, 2000 and 1000 nodes long, with a different last leaf in subRoot, reach this bound.
  • Space: O(h1 + h2), where h1 and h2 are the heights of the two trees. The isSubtree calls stack up along one path of root, and the comparison running on top of them adds at most one frame per level of subRoot.

The inner check on its own is Same Tree, and comparing a tree with its mirror image is Symmetric Tree.