Invert, mirror and symmetry checks in Python

Why this matters

A mirror image is what you see in a mirror: left and right are swapped. Software meets this idea often. A right-to-left layout reverses the order of items on a screen. A palindrome check compares the two ends of a word and works inward. A tree version asks a simple question: if you flip one side of the tree over, does it match the other side?

This lesson covers three tasks that use the same two-branch pattern. Inversion swaps the children of every node. A mirror check compares two trees by walking them in opposite directions. A symmetry check asks whether one tree mirrors itself. Inversion is a short warm-up, and the symmetry check is a common interview question, because the answer depends on comparing two nodes at a time instead of one.

The same tree and subtree checks lesson later in this module compares two trees in the same direction. This lesson changes that direction, which changes the rule.

Words you will need

• Mirror image: the reverse of something left to right. For a tree, the mirror image has every node's left and right children swapped, at every level.
• Invert: swap the left and right children of every node in a tree. The result is the mirror image of the original.
• Symmetric: a tree is symmetric when its left side is a mirror image of its right side.
• Swap: exchange two values. A swap needs a saved copy of one value first. Without that copy, one value is lost.
• Queue: a line where items leave in the order they arrived. The first item in is the first item out. popleft() removes the front item from a deque.
• None: Python's word for "no object here". An empty child is None.
• deque: a double-ended queue from the collections module. It accepts None as an item, which the symmetry check needs.

Part 1: invert a tree

Start with a small tree.

    1
   / \
  2   3
 /
4

The root 1 has children 2 and 3. Node 2 has one left child, 4. Node 3 has no children.

Inverting swaps the children of every node. Node 1 swaps 2 and 3. Node 2 has no right child to start with, so its single child 4 moves from the left side to the right side. The result is:

    1
   / \
  3   2
       \
        4

The rule for one node is short, and the order of steps matters.

1. Save the left child in a variable, called old_left here. Without this step the left child is lost.
2. Set the left child to the inverse of the right child.
3. Set the right child to the inverse of the saved left child.
4. Return the node.

The saved copy is what makes the swap work. If you skip step 1 and write node.left = invert(node.right) followed by node.right = invert(node.left), the second line reads the new left child, which is the old right child, and the old left subtree disappears. The mistakes section shows this.

Here is a trace of the function on the tree above.

• invert(1) saves old_left as node 2. Then it sets node.left to invert(3), which returns 3 because 3 has no children. Then it sets node.right to invert(2).
• invert(2) saves old_left as node 4. It sets node.left to invert(None), which is None. It sets node.right to invert(4), which returns 4.
• Node 2 now has no left child and 4 on the right. It is returned to the root.
• The root ends with 3 on the left and 2 on the right.

The function changes the tree in place, so it rearranges the same nodes instead of making copies. It also returns the root, so the caller can write mirrored = invert(root) if it wants to use the result right away.

Part 2: compare a tree with a mirror image

Inversion changes one tree. A mirror check compares two trees that are separate objects. The question is: is tree b the mirror image of tree a?

Walk the two trees together, but cross the pairs. The left side of a is compared with the right side of b, and the right side of a is compared with the left side of b. Think about a mirror: the outer edge of the left side faces the outer edge of the right side. Matching outer with outer and inner with inner is what a mirror does.

The rule has three cases.

1. If both nodes are None, the two empty spots match. Return True.
2. If only one node is None, the shapes differ. Return False.
3. Otherwise, the values must be equal, and both pairs of children must mirror each other. The pairs are a.left with b.right, and a.right with b.left.

Here are two trees that are mirror images of each other.

Tree a            Tree b
    1                 1
   / \               / \
  2   3             3   2
 / \                  / \
4   5                5   4

Walk the pairs.

• The roots are both 1, so the values match.
• The pair a.left and b.right is 2 and 2. The values match. Next, a.left.left (4) pairs with b.right.right (4), and a.left.right (5) pairs with b.right.left (5). Both match.
• The pair a.right and b.left is 3 and 3. They are leaves (nodes with no children), so the match holds.

Every pair matches, so the trees are mirror images.

A tree compared with itself is not a mirror image of itself, unless it is symmetric. Compare a with a: the first pair is a.left (2) with a.right (3). The values differ, so the answer is false. Part 3 uses the same idea on one tree.

Part 3: symmetry of one tree

A tree is symmetric when its left subtree is a mirror image of its right subtree. The root itself is not compared with anything. The check starts from the two children of the root.

      1
    /   \
   2     2
  / \   / \
 3   4 4   3

This tree is symmetric. The left child 2 and the right child 2 match in value. The left side's left child 3 matches the right side's right child 3. The left side's right child 4 matches the right side's left child 4.

Now a tree that looks symmetric at the top, but is not.

    1
   / \
  2   2
   \   \
    3   3

The two children of the root are both 2. The values match, so a check on the top two values alone would say yes. The left side has a child on the right, and the right side has a child on the right too. A mirror would need the right side to have its child on the left. So the answer is no. The mistakes section shows the wrong check that says yes here.

Here is how the two checks run on these trees.

• The symmetric tree: the pair of root children is 2 and 2, the next pair is 3 and 3, and the next pair is 4 and 4. Every pair matches, so the answer is True.
• The second tree: the pair of root children is 2 and 2, which match. Then the pair left.left with right.right is None and 3. One is None, so the answer is False.

Part 4: the same check with a queue

The recursive check uses the call stack, the record of function calls that are still running. It can also be written with a queue, which keeps the pairs in order and checks them one after another.

The idea is the same. Start with the pair of root children. Take two nodes from the front of the queue. If both are None, skip the pair. If one is None, or their values differ, the answer is false. Otherwise add two new pairs to the back of the queue: a.left with b.right, and a.right with b.left. When the queue is empty, every pair has matched.

Items go into the queue in pairs, so each time two items are taken out, they form a pair. The code takes two items with two popleft() calls.

Use collections.deque here. It accepts None as an item, which the queue needs, because an empty child is added to the queue as None.

The full program

The file below has the inversion function, the mirror check, the recursive and queue symmetry checks, and four examples. Each example prints one or two results.

Run it with python3 on the file that holds this code.

The output is:

Example 1 before: (1 (2 (4 None None) None) (3 None None))
Example 1 after:  (1 (3 None None) (2 None (4 None None)))
Example 2 mirror of a and b: True
Example 2 mirror of a and a: False
Example 3 symmetric recursive: True
Example 3 symmetric iterative: True
Example 4 symmetric recursive: False
Example 4 symmetric iterative: False

The show function prints each node as (value left right), and None for an empty child. The first line of the output matches the drawing of the original tree, and the second line matches the inverted tree.

Common mistakes

Mistake 1: overwriting the left child before saving it

This version of invert does not save the old left child.

Run it on the first example tree. The output is:

Wrong invert: (1 (3 None None) (3 None None))

The line node.left = invert_wrong(node.right) puts the right subtree on the left. The next line reads node.left for the right side, but that attribute now holds the old right subtree. So the right side points at the same right subtree again, and the old left subtree (node 2 with node 4) is gone. The fix is the saved copy from step 1 in Part 1.

Mistake 2: comparing only the two children's values

A quick check for symmetry compares only the values of the root's two children.

On example 4, it prints True:

Top-two check on example 4: True

Example 4 is not symmetric, because the 3s are on the same side of both 2s. The check looks at one level only. It never reaches the 3s. The recursive check in Part 3 goes down the tree, and it finds the difference.

Mistake 3: forgetting that a queue item can be None

In Java, ArrayDeque refuses null items, so a queue version fails at the moment the empty child is added. Python's deque accepts None, so the same mistake appears later and looks different. If the code reads a field such as .val from a None item, Python stops with an AttributeError. The check if a is None and b is None before the attribute reads is what prevents it.

from collections import deque
 
 
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def is_symmetric_no_check(root):
    queue = deque([root.left, root.right])
    while queue:
        a = queue.popleft()
        b = queue.popleft()
        if a.val != b.val:
            return False
        queue.append(a.left)
        queue.append(b.right)
        queue.append(a.right)
        queue.append(b.left)
    return True
 
 
s1 = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)),
              TreeNode(2, TreeNode(4), TreeNode(3)))
print(is_symmetric_no_check(s1))

The output is:

Traceback (most recent call last):
  File "main.py", line 27, in <module>
    print(is_symmetric_no_check(s1))
          ~~~~~~~~~~~~~~~~~~~~~^^^^
  File "main.py", line 16, in is_symmetric_no_check
    if a.val != b.val:
       ^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The first pair the code checks is the two 2s, which match. Their children are added to the queue. The leaves have no children, so None values go into the queue. Next, a pair of None values comes out, and the code reads .val from one of them. The file path and caret marks depend on the Python version and where the file is saved. The fix is the None check before any attribute is read, as the working version does.

Practice

Exercise 1. The tree has root 1, left child 2, and right child 3. Both children are leaves. Write the tree after inversion in the same form the program prints.

Show the answer

(1 (3 None None) (2 None None)). The root's two children swap, and the leaves have no children to move.

Exercise 2. Is this tree symmetric? The root is 5. Its left child is 1, with a right child 2. Its right child is 1, with a left child 2.

Show the answer

Yes. The two 1s match. The pair left.left with right.right is None and None, so it matches. The pair left.right with right.left is 2 and 2, which are leaves, so it matches. The answer is True.

Exercise 3. Is this tree symmetric? The root is 1, with a left leaf 2 and a right leaf 2.

Show the answer

Yes. The two children have the same value, and both have no children. The answer is True.

Exercise 4. Tree A has root 1, with a left child 2, and 3 as the left child of that 2. Tree B has root 1, with a right child 2, and 3 as the right child of that 2. Are they mirror images of each other?

Show the answer

Yes. Tree B is the mirror image of tree A. The pair of roots is 1 and 1. The pair A.left with B.right is 2 and 2. Their children are 3 and 3, on the outer side of each tree. The other pairs are None with None. The call is_mirror(A, B) returns True.

Exercise 5. Suppose the mirror check were written as is_mirror(a.left, b.left) instead of is_mirror(a.left, b.right). Apply that to example 3, with a as the root's left child and b as the right child. What does it return, and why is that wrong?

Show the answer

It returns False. The left subtree of example 3 has 3 on its left, and the right subtree has 3 on its right. Comparing the two left children gives 3 against 4, which differs, so the check says false. But example 3 is symmetric, so the correct answer is True. The pairing must cross, so that the outer side of one side meets the outer side of the other.

Summary

• Inversion saves the left child before it overwrites anything, then swaps the two recursive results.
• A mirror check takes two trees, and compares left with right and right with left.
• A symmetry check is a mirror check between the root's two children.
• The queue version keeps pairs in order. A deque in Python holds None items, so the None check must come before every attribute read.
• A check on only the top level of a tree gives a wrong yes for trees that differ lower down.