Given two binary trees, decide whether the second appears as a subtree of the first (same structure and values from some node down). Then optimise your solution.

Approach

Any match has to start at some node of root, so visit every node and ask whether the tree starting there is identical to sub_root. The identical-tree check is the usual recursion: empty matches empty, an empty node never matches a non-empty one, and otherwise the values and both pairs of children have to match. If no node in root produces a match, the answer is false.

Steps

1. If root is empty, return false.
2. If the tree starting at root is the same as sub_root, return true.
3. Otherwise, return whether sub_root is a subtree of root.left or of root.right.

Complexity

• Time: O(m · n) in the worst case, where m and n are the sizes of the two trees. Each node of root can start a comparison that walks all of sub_root.
• Space: O(h) for the recursion stack, where h is the height of root.

Common mistakes

• Accepting a match when only the top of the tree agrees. The subtree in root has to end exactly where sub_root ends, with no extra descendants.
• Writing trees as strings without separators. [12] and [2] would give 12 and 2, and 2 appears inside 12, even though neither tree contains the other.