Subtree of Another Tree

Is tree sub a subtree of tree root? A subtree consists of some node of root and all of its descendants — the whole thing must match sub exactly (same shape, same values).

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: two trees, one per line: root, then sub (both non-empty).

Output: true or false.

Constraints: 1 ≤ nodes ≤ 2000 in root, 1 ≤ nodes ≤ 1000 in sub; values are small, so many nodes look alike. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: for every node of root, run Same Tree against sub — O(m·n), fine here. Faster: serialise both trees (with null markers!) and search one string in the other.