Same Tree

Problem

You are given the roots of two binary trees, p and q. Decide whether the two trees are identical: they must have the same shape, and corresponding nodes must hold equal values. Return True if they are identical and False otherwise.

• Each tree has at most 5,000 nodes.
• Node values are integers; duplicates are allowed within a tree.
• Either tree may be empty.

Examples

• p = [6, 3, 8, 1], q = [6, 3, 8, 1] → True. Same shape, same values.
• p = [2, 5], q = [2, None, 5] → False. The values match but the 5 is a left child in one tree and a right child in the other.
• p = [4, 1, 4], q = [4, 4, 1] → False. Same shape, values differ at the children.

Hints

1. When are two empty trees the same? When is an empty tree the same as a non-empty one?
2. If the two roots agree, what needs to be true about the two left subtrees and the two right subtrees?
3. Recurse in lockstep over both trees: equal-null, equal-value, and recursive equality of both child pairs.