Are two trees identical?

Trees Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

Two different shapes, same in-order values. What does this print?

Python 3.13
def inorder(level: list[int | None], i: int = 0) -> list[int]:
    if i >= len(level) or level[i] is None:
        return []
    v = level[i]
    assert v is not None
    return inorder(level, 2 * i + 1) + [v] + inorder(level, 2 * i + 2)

a: list[int | None] = [2, 1]
b: list[int | None] = [1, None, 2]
print(inorder(a) == inorder(b), a == b)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True False

Right: both walk as [1, 2], but the shapes differ.

One traversal order cannot tell these shapes apart, which is why the check compares structure and values together.

Why not the others?
  • B True True. The lists describing the trees are different.
  • C False False. Both in-order walks give [1, 2].

30-second answer

Recurse on both trees together: two empty trees match, one empty and one not do not, otherwise the roots must hold equal values and both pairs of children must match. O(n) time for the smaller tree, O(h) stack.

Practise saying it · 30 s. No recording, just a timer

Explain how to compare two trees.

Say your answer out loud, then check which of these points you covered:

  • Recurse on both
  • Base cases for None
  • O(n)

Deep dive

The base cases do most of the work: handle (None, None) and (None, node) before touching values.

Comparing in-order lists alone is not enough; different shapes can give the same in-order sequence.

With dataclass nodes, a == b compares fields recursively and gives the same answer, but explain the recursion anyway.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def identical(a: Node | None, b: Node | None) -> bool:
    if a is None or b is None:
        return a is b
    return (a.val == b.val and identical(a.left, b.left)
            and identical(a.right, b.right))

Common mistakes

  • Comparing only values in one traversal order.
  • Accessing .val before checking for None.

Senior take & follow-ups

Write the three base cases first; the rest is one line.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you check whether one tree appears inside another?

    Show hint

    For each node of the big tree, run this check: O(n·m), or serialise both and search the string.

  2. What about mirror images?

    Show hint

    Compare left with right and right with left.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.