Subtree of Another Tree

Easy Problem 69 of 151 Java and Python

Problem

Given the roots of two binary trees root and subRoot, return true if root has a subtree with exactly the same structure and values as subRoot.

A subtree is a node together with all of its descendants.

Example 1

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true

Example 2

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false
Why: The 4-subtree in root also contains 0.

Constraints

1 ≤ nodes in root ≤ 2000, 1 ≤ nodes in subRoot ≤ 1000

Explanation

Try every node of root as a possible match and run Same Tree from there.

Faster: serialize both trees with null markers and separators, and check whether one string contains the other. Wrapping each value in delimiters stops "2" from matching inside "12".

Approach 1 · Naive

Same Tree at every node

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

For each node in root, check whether the tree starting there equals subRoot.

If root is null, return false.
Return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).

Java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return same(root, subRoot) || 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);
    }
}

Python

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(a, b):
            if not a or not b:
                return a is b
            return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)

        if not root:
            return False
        return same(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Approach 2 · Optimal

Serialize and search

Time O(m + n) with a linear string search such as KMP (library `contains` is fast in practice)
Space O(m + n)

Preorder-serialize both trees with null markers and delimiters, then check substring containment.

Serialize as ^value for nodes and # for null, in preorder.
Return whether serialize(root) contains serialize(subRoot).

Java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return serialize(root, new StringBuilder()).toString()
            .contains(serialize(subRoot, new StringBuilder()).toString());
    }

    private StringBuilder serialize(TreeNode node, StringBuilder out) {
        if (node == null) {
            return out.append(",#");
        }
        out.append(",^").append(node.val);
        serialize(node.left, out);
        return serialize(node.right, out);
    }
}

Python

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node, out):
            if not node:
                out.append(",#")
                return out
            out.append(f",^{node.val}")
            serialize(node.left, out)
            return serialize(node.right, out)

        return "".join(serialize(subRoot, [])) in "".join(serialize(root, []))

Complexity compared

Approach	Time	Space
Naive Same Tree at every node	O(m · n)	O(h)
Optimal Serialize and search	O(m + n) with a linear string search such as KMP (library `contains` is fast in practice)	O(m + n)

Key takeaways

Delimiters matter: without them, a tree [12] would wrongly "contain" [2].

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem