Subtree of Another Tree: the idea to remember.

The core insight

At each node, check exact tree equality; if it fails, try both child roots.

Why it works

A matching subtree must have some root in the larger tree. Testing every such root and comparing the full structure covers all possibilities.

The mistake to avoid

Matching the root value alone is insufficient. Missing children must match missing children.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

boolean isSubtree(TreeNode root, TreeNode sub) {
    if (sub == null) return true;
    if (root == null) return false;
    return same(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub);
}
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);
}

Make the next connection