272. Subtree of Another Tree

Try matching subRoot against the tree rooted at each node of root. Two trees are identical when their roots match and their left and right subtrees match recursively.

Two nested recursions

1. sameTree(a, b): both null → true; one null → false; else a.val == b.val and the left and right subtrees match.
2. dfs(node): if sameTree(node, subRoot), found it; otherwise recurse into node.left and node.right.

Walk-through

dfs(node):
    if node is None: return False
    if sameTree(node, subRoot): return True
    return dfs(node.left) or dfs(node.right)

Worked example

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

• At node 3: not equal to subRoot.
• At node 4 (left child): sameTree(4[1,2], 4[1,2]) → true. Return true.

Complexity

• Time: O(m · n) — for each of m nodes in root we may compare against n nodes of subRoot.
• Space: O(h) recursion depth.

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (same(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    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);
    }
}