Subtree of Another Tree

Problem

You are given the roots of two binary trees, root and subRoot. Return True if some node in root has a subtree that is identical to subRoot, meaning the same shape and the same values at every position. A node's subtree consists of that node and all of its descendants, so matching only the top few levels of subRoot does not count.

• root has between 1 and 5,000 nodes; subRoot has between 1 and 2,500 nodes.
• Node values are integers and may repeat many times within a tree.

Examples

• root = [8, 3, 10, 1, 6, None, 14, None, None, 4, 7], subRoot = [6, 4, 7] → True. The node 6 in root has children 4 and 7 and nothing below, exactly like subRoot.
• root = [8, 3, 10, 1, 6, None, 14, None, None, 4, 7, None, None, None, None, None, 9], subRoot = [6, 4, 7] → False. The node 6 looks right at first, but its child 7 now has a right child 9 that subRoot lacks.
• root = [5], subRoot = [5] → True. A tree is a subtree of itself.

Hints

1. You already know how to check whether two trees are identical. Where in root could the match start?
2. Try every node of root as a candidate starting point. What is the worst-case cost of that, and when does it happen?
3. To go faster, turn each tree into a string with explicit null markers and delimiters, then use linear-time substring search (KMP), or hash subtrees bottom-up.