Same Tree

Return true if two binary trees have the same structure and the same values at every position.

A way to picture it

Two friends compare their family trees by walking them in perfect lockstep, one generation at a time. The instant one has a relative where the other has an empty spot — or the names differ — the trees aren't the same.

How to approach it

Both null → match. One null → mismatch. Otherwise the values must match and both pairs of subtrees must match.

Example

Input: {"p":[1,2,3],"q":[1,2,3]}. Output: true.

Complexity: O(n) time and O(h) space. Each pair of nodes is compared at most once.

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