LeetCode 101 · Trees · DFS

Symmetric Tree, explained with a picture

Holding a tree up to a mirror.

Trees · DFS
▶ Watch it step by step

The problem

Decide whether a binary tree is a mirror image of itself around its centre.

Input:  [1, 2, 2, 3, 4, 4, 3]
Output: true

Picture it

Picture holding the tree up to a mirror down its middle. Compare the outer pair (left’s left with right’s right) and the inner pair (left’s right with right’s left), all the way down.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Recursive mirror check on pairs of nodes. O(n).

Python solution

def is_symmetric(root):
    def mirror(a, b):
        if not a and not b:
            return True
        if not a or not b or a.val != b.val:
            return False
        return mirror(a.left, b.right) and mirror(a.right, b.left)
    return mirror(root.left, root.right)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.