Subtree of Another Tree

Return true if subRoot appears somewhere inside root as an exact subtree — a node plus all of its descendants.

A way to picture it

You've found a jigsaw piece and want to know where it came from. Hold it against every spot on the finished puzzle. At each spot, check that it matches perfectly — not just the edge you're touching, but every nook all the way down.

How to approach it

For every node in root, check sameTree(node, subRoot). The first full match wins.

Example

Input: {"root":[3,4,5,1,2],"subRoot":[4,1,2]}. Output: true.

Complexity: O(m · n) time and O(h) space. A full comparison may start at each of the m nodes.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.