Symmetric Tree

def is_symmetric(root):
    def is_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 (is_mirror(a.left, b.right) and
                is_mirror(a.right, b.left))
    return is_mirror(root.left, root.right)

Symmetric Tree. Given the root of a binary tree, is it a mirror of itself? Like a butterfly, the left wing must match the right wing, spot for spot, across the middle.

Here, one has two and two below it, then three, four, four, three. Each side mirrors the other: true. In the second tree, both threes hang to the right, so the wings don't match: false.

The obvious way: build a mirrored copy of the whole tree, then compare the two, node by node. That's O of n time, but the copy costs O of n extra space.

Better: check the wings against each other directly, one pair at a time. Two nodes mirror each other if their values match, their outer children mirror, and their inner children mirror. Two empty spots match. One empty spot doesn't.

In code, is mirror takes a pair. Both empty: true. One empty, or different values: false. Otherwise, check the outer pair and the inner pair. Start with the root's two children.

Walking it: two and two match. Outer pair: three and three match, and their empty children match too. Inner pair: four and four match. Every pair holds, so the tree is symmetric. In the second tree, two and two match, but the outer pair is empty against three: false, right away.

Each node is checked once: O of n time, and O of h space for the recursion, h being the tree's height.

Compare the pairs: outer with outer, inner with inner. That's Symmetric Tree.