Does a tree mirror itself?

Trees Junior Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Which pairs must be compared at each step?

Options

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

Show answer

Answer: A Outer children with each other, and inner children with each other

Right: a reflection swaps left and right at every level.

Reflection maps the far left onto the far right, so the comparisons cross over at every depth.

Why not the others?
  • B Each node's left child with its own right child. That only checks one level, not the whole reflection.
  • C Left with left, right with right. That is the identical-trees check, not a reflection.

30-second answer

A tree mirrors itself if its left and right subtrees are mirrors of each other. Two subtrees are mirrors when their roots match, the outer pair (left.left, right.right) are mirrors and the inner pair (left.right, right.left) are mirrors. O(n) time, O(h) stack.

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

Explain the mirror check.

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

  • Mirror of left and right subtrees
  • Cross the pairs
  • O(n)

Deep dive

It is the identical-trees check with the children crossed.

An iterative version pushes pairs onto a queue in the same crossed order.

Comparing row values for palindromes fails when None gaps are ignored.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def mirrors_itself(root: Node | None) -> bool:
    def pair(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 pair(a.left, b.right)
                and pair(a.right, b.left))
    return root is None or pair(root.left, root.right)

Common mistakes

  • Checking only that each row reads the same both ways without counting gaps.
  • Comparing left.left with right.left (not crossed).

Senior take & follow-ups

Point out the crossed pairing; it is the only difference from the identical-trees check.

Follow-up questions

Think of your answer first, then open the hint.

  1. Can you do it without recursion?

    Show hint

    Yes: a queue of node pairs, pushing outer and inner pairs each step.

  2. What does 'mirror' mean for values only vs shape?

    Show hint

    Both must match; a shape-only question drops the value comparison.

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.