Subtree of another tree

Given two binary trees, root and subRoot, return whether some node of root has a subtree identical to subRoot.

Before you code

A subtree must match all the way down: in the second example, 4's subtree has an extra node 0, so it doesn't match. Reuse a same-tree check.

Hints

1. is_subtree(root, sub) is true if same(root, sub), or if sub is a subtree of root's left or right child.
2. This is O(m × n) in the worst case.
3. Faster: serialize both trees with null markers and check whether one string contains the other, using a linear-time string search.

Production & complexity notes

When solving Subtree of another tree on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Tree recursion patterns to reinforce the underlying pattern.

What it practices

Combining two recursive functions, from Tree recursion patterns.