Subtree of Another Tree

Problem

Given two binary trees root and subRoot, return true iff subRoot appears (with the same structure and values) anywhere inside root.

Constraints

• 1 ≤ root nodes ≤ 2000
• 1 ≤ subRoot nodes ≤ 1000

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def isSubtree(self, root, subRoot):
        def same(a, b):
            if not a and not b:
                return True
            if not a or not b or a.val != b.val:
                return False
            return same(a.left, b.left) and same(a.right, b.right)
        if not root:
            return subRoot is None
        if same(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode sub) {
        if (root == null) return false;
        return same(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub);
    }
    private boolean same(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.