Are these two trees identical

Given two binary trees, say whether they are identical: the same shape, with the same value at every matching position.

How the input is written#

Two trees, each a count then that many level order tokens with null for a missing child.

Worked example#

1 2 3 against 1 2 3:

    1          1
   / \        / \
  2   3      2   3

Same shape, same values, so true.

Now 1 2 against 1 null 2:

    1          1
   /            \
  2              2

Both hold the values 1 and 2, and they are not the same tree. One has a left child and the other a right child. So false.

That pair is the whole reason this problem exists: comparing the values a tree contains is not the same as comparing the tree.

The idea#

Two trees match when:

1. both are missing, which counts as a match, or
2. neither is missing, their values are equal, and their left subtrees match and their right subtrees match.

Anything else is a mismatch, including one missing and the other not.

same(a, b):
    if both missing        -> true
    if only one missing    -> false
    if values differ       -> false
    return same(a.left, b.left) and same(a.right, b.right)

The order of those checks matters. Reading a.val before checking whether a is missing is how this crashes.

The cost#

Time O(n) where n is the size of the smaller tree, because the walk stops at the first disagreement. Memory O(h) for the call stack.

Constraints#

• 0 <= number of nodes in each tree <= 10000
• -10000 <= value <= 10000