Inverting a Binary Tree

Swap the left and right children of every node. The recursive version returns the inverted subtree so that you can assign both children in one statement, which keeps the swap and the recursion together.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def invert(root):
    if root is None:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root


def to_list(node, out=None):
    if out is None:
        out = []
    if node:
        out.append(node.value)
        to_list(node.left, out)
        to_list(node.right, out)
    return out


tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
print(to_list(tree))
print(to_list(invert(tree)))

The outputs are 4, 2, 1, 3, 7, 6, 9 and 4, 7, 9, 2, 6, 3, 1. The second list is the first one reflected left to right, with the whole tree mirrored.

The mechanism is that the mirror of a mirror is the original, so you have to invert the children before you swap them. Inverting the right subtree and the left subtree first and then swapping them produces the mirror of the whole subtree, which is exactly what the parent needs. Doing the swap before the recursion would give the wrong answer, because the children would be swapped back by the recursive calls.

The trade-off to name is that the recursion mutates the tree in place, so any other reference to the same nodes sees the inverted structure. If the original tree is needed, you have to copy it first. The cost is linear time with stack space proportional to the height, and for a very deep tree the iterative version in the next answer avoids the stack entirely while doing exactly the same swap on every node.

Do a breadth first traversal and swap the children of each node as you visit it. Because the inversion of a node does not depend on its children, the order in which you visit them does not matter.

from collections import deque


class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def invert(root):
    if root is None:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root


def to_list(node, out=None):
    if out is None:
        out = []
    if node:
        out.append(node.value)
        to_list(node.left, out)
        to_list(node.right, out)
    return out


tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
print(to_list(invert(tree)))

The output is 4, 7, 9, 2, 6, 3, 1, the same mirrored tree the recursive version produces.

The mechanism is that the swap is a local operation. Each node's children are exchanged, and since every node is visited exactly once, every node ends up mirrored. There is no ordering constraint here, unlike in the recursive version where the children must be inverted before they are swapped, and that difference is the interesting part of the comparison.

The trade-off to name is memory. A breadth first traversal holds a queue proportional to the width of the tree, while the recursive version holds stack frames proportional to the height. For a wide tree the queue is the bigger problem, and for a deep tree the stack is. A depth first traversal with an explicit stack keeps the memory proportional to the height without any risk of a stack overflow, so it is the most robust of the three. All three run in linear time, because the work is one swap per node.