DSA · Trees · #171

Subtree of Another Tree

Module 44 · difficulty 2/5·⏱ 30:00starts on first keystroke

Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of `root` with the same structure and node values as `subRoot`, and `false` otherwise. A subtree of a tree `t` is a tree consisting of a node in `t` and all of its descendants. The tree `t` itself may also be considered a subtree of itself. Implement the function `isSubtree(root, subRoot)`. Each node is `{ val, left, right }` with `null` for missing children.

Examples

root = [3,4,5,1,2], subRoot = [4,1,2] → true — The subtree rooted at the node with value 4 matches subRoot exactly.
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] → false — The candidate subtree rooted at 4 has an extra child 0, so it does not match.
root = [1,1], subRoot = [1] → true — A single-node subRoot matches the leaf node with value 1.

Constraints

· The number of nodes in the root tree is in the range [1, 2000].
· The number of nodes in the subRoot tree is in the range [1, 1000].
· -10^4 <= Node.val <= 10^4

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.