Is a binary tree symmetric about its root? How might one determine this?

There is a whole menagerie of binary-tree-questions that all reflect the same pattern of recursive thinking. I have a whole list here. Presented as a battery, it’s a nice way to build up recursive thinking muscles. Presented in isolation, it feels like an unpleasant surprise to do this sort of unusual problem-solving. Here’s the reasoning

1. We do the base case.
2. We imagine we have the answer for our smaller problems.
3. We recombine those answers into our main answer.

The extra “half-step” here is that we need to realize that we want to be asking if our 2 children are symmetric. So while our initial input takes a single root, we’ll want to defer to an implementation of something like isMirror(root.left, root.right), which asks if the first parameter is a tree that is a mirror-image of the right. This is sort of a reduction: the tree root is symmetric if the two subtrees root.left and root.right are mirror-images of each other.

So, let’s use the 3 steps to implement isMirror(a, b), where a and b are two trees.

Applying the Skeleton

1. Base cases: if they’re both empty (None or null or whatever), they’re mirror images. Return true, done! If only one is empty, they can’t be mirrors. Return false, done! If a and b have different root values, well then they’re not mirrors, so return false done! (That last case may be the most subtle. I can’t explain it better in this blog-post format).
2. So far, at the “root” level, our two trees seem like mirror-images. Great. What we want now is a.left to be a mirror of b.right. (Note the left-versus right!) and a.right to be a mirror of b.left. We pretend we already have the answers.
3. So if both those cases are true, our original trees are mirrors of each other. We’re done, return true! (Or false, if either of those recursive calls were false).

This question seems like a much-more-complicated version of tree equality. One might be (as I was) suspicious of whether the comparison in step 2 is exactly correct. It may be a sort of parity problem, where you only want to “flip” the left-versus-right comparison, and doing it on the 2nd or 3rd recursive layer will erroneously undo the mirroring. As it happens, this is simply not the case, but I think it’s very forgivable to act hesitantly in light of that concern.

def isMirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    if a.val != b.val:
        return False
    return isMirror(a.left, b.right) and isMirror(a.right, b.left)
class Solution(object):
    def isSymmetric(self, root):
        if root is None: return True
        return isMirror(root.left, root.right)