DSA Inverting a Binary Tree

The problem

Inverting a binary tree swaps the left and right child of every node. Every node keeps its value. Only the two child links trade places.

The result is the mirror image of the original tree. A value that sat in a left subtree sits in the matching right subtree afterwards, at the same depth.

The operation changes the tree in place. The input is the root of the tree, and the output is that same root, with the tree under it mirrored.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def shape(node):
    if node is None:
        return None
    return (node.value, shape(node.left), shape(node.right))

main = TreeNode(4,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(7, TreeNode(6), TreeNode(9)))
print("main before:", levels(main))
print("main after, expected:", [[4], [7, 2], [9, 6, 3, 1]])
single = TreeNode(8)
print("single before:", levels(single), "after, expected:", [[8]])
skewed = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
print("skewed before shape:", shape(skewed))
print("skewed after shape, expected:", (1, (2, (3, None, None), None), None))
print("empty before:", levels(None), "after, expected:", [])

Read the main case by levels. Each level holds the same values before and after, in reverse order. That reversal on every level is the visible signature of a full inversion.

The skewed case needs the shape view instead of levels. Its levels are [[1], [2], [3]] on both sides, because each level holds one value. The nested shape shows which side each node hangs from, and that is what flips.

Intuition: swapping only the root mirrors only the top

A first idea swaps the children of the root and stops. The top of the tree looks mirrored. Everything below the two swapped subtrees keeps its old shape.

The flaw is easy to miss in a small drawing. The subtrees moved as whole blocks, but their insides did not turn around. A mirror image has to turn every level, not just the first one.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

tree = TreeNode(4,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(7, TreeNode(6), TreeNode(9)))
print("before:", levels(tree))
tree.left, tree.right = tree.right, tree.left
print("after root swap only:", levels(tree))
print("full inversion, expected:", [[4], [7, 2], [9, 6, 3, 1]])

The second level is right and the third level is wrong. It reads [6, 9, 1, 3], where a full inversion needs [9, 6, 3, 1]. Each pair inside a subtree is still in its original order.

The repair is repetition. Swap at the root, then do the same swap inside each subtree, all the way down. Every node gets its one swap.

Brute force: build a mirrored copy

The straightforward method builds a brand-new tree. Each new node copies a value from the original. Its left child is a mirrored copy of the original right subtree, and its right child is a mirrored copy of the original left subtree.

The copy is easy to reason about, because the original is never touched. Its cost is a whole second tree. The code counts the new nodes it allocates.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

made = 0

def mirror_copy(node):
    global made
    if node is None:
        return None
    made += 1
    return TreeNode(node.value, mirror_copy(node.right), mirror_copy(node.left))

tree = TreeNode(4,
                TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(7, TreeNode(6), TreeNode(9)))
copy = mirror_copy(tree)
print("copy levels:", levels(copy))
print("original levels:", levels(tree))
print("new nodes made:", made)

The copy is a correct mirror, and the original still shows its starting levels. The bill is seven new nodes for a seven-node tree. Every inversion pays for a full second tree and then has to dispose of the first one.

Nothing about the task requires a second tree. A swap exchanges two links that already exist. Doing the swaps inside the original tree removes the allocation cost entirely.

The optimal solution: swap in place, node by node

Recursion here means a function that swaps one node, then calls itself on each child. The children it visits after the swap are the same subtrees, now sitting on opposite sides.

The key idea is one sentence. Swapping the two children at every node, exactly once per node, turns the whole tree into its mirror image, because every subtree is itself swapped by the same rule.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def shape(node):
    if node is None:
        return None
    return (node.value, shape(node.left), shape(node.right))

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

def make_main():
    return TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(7, TreeNode(6), TreeNode(9)))

main = invert(make_main())
print("main after:", levels(main))
print("single after:", levels(invert(TreeNode(8))))
print("empty after:", levels(invert(None)))
skewed = invert(TreeNode(1, None, TreeNode(2, None, TreeNode(3))))
print("skewed after shape:", shape(skewed))

All four cases from the start of the article pass. The empty tree returns None at once, so an empty input is handled by the same base case that stops the recursion at every missing child.

The function returns the root it was given. The returned tree is the input tree, changed. No new TreeNode is created anywhere in the function.

Walkthrough: swaps on a five-node tree

Follow a smaller tree through the swaps in the order the recursion makes them. The tree is a root 4, a left child 2 with leaves 1 and 3, and a right leaf 7.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def invert_traced(node, root):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    print("swapped at", node.value, "-> levels:", levels(root))
    invert_traced(node.left, root)
    invert_traced(node.right, root)
    return node

tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
print("before:", levels(tree))
invert_traced(tree, tree)
print("final:", levels(tree))

The root swap moves the whole subtree rooted at 2 to the right side. Its inside still reads 1 then 3 at that moment. Only the later swap at node 2 turns that pair into 3 then 1.

The swaps at nodes 7, 3, and 1 change nothing visible, because both children of each are missing. The recursion still visits them. Every node is visited, whether or not its swap has an effect.

Complexity

Time is O(n). The recursion visits each node once and swaps once there, so the swaps equal the node count.

Space is O(h) of extra memory, where h is the depth of the tree in edges. The swaps reuse the existing nodes, and the only extra memory is the call stack, one frame per level on the current path.

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

swaps = 0
made = 0

def invert(node):
    global swaps
    if node is None:
        return None
    swaps += 1
    node.left, node.right = node.right, node.left
    invert(node.left)
    invert(node.right)
    return node

def mirror_copy(node):
    global made
    if node is None:
        return None
    made += 1
    return TreeNode(node.value, mirror_copy(node.right), mirror_copy(node.left))

def balanced_of(values):
    if not values:
        return None
    mid = len(values) // 2
    return TreeNode(values[mid], balanced_of(values[:mid]), balanced_of(values[mid + 1:]))

for size in [3, 7, 15]:
    values = list(range(1, size + 1))
    swaps = 0
    invert(balanced_of(values))
    made = 0
    mirror_copy(balanced_of(values))
    print("nodes:", size, "in-place swaps:", swaps, "copy allocations:", made)

Both methods touch every node, so their counts match. The difference is what the touches cost. The in-place method allocates nothing, and the copy method allocates one new node per old node.

Edge cases and pitfalls

An empty tree inverts to an empty tree. A single node inverts to itself, because its two missing children swap with no effect. A skewed tree flips its lean, from the right side to the left side or back.

Inverting twice restores the original tree exactly. Each swap is its own undo, and the second pass applies every swap again.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def shape(node):
    if node is None:
        return None
    return (node.value, shape(node.left), shape(node.right))

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

def make_main():
    return TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(7, TreeNode(6), TreeNode(9)))

print("empty:", invert(None))
print("single after:", levels(invert(TreeNode(8))))
skewed = invert(TreeNode(1, None, TreeNode(2, None, TreeNode(3))))
print("skewed after shape:", shape(skewed))
tree = make_main()
invert(tree)
invert(tree)
print("twice restores:", levels(tree))

The in-place change is itself a pitfall. After one inversion the original arrangement is gone, because the same nodes now form the mirror. Code that still needs the original order must save its level list, or build a copy, before inverting.

A second pitfall lives in the swap line. Writing the two assignments one at a time, without the paired form, overwrites the first child before it is read. Both subtrees then point at the same child, and the other subtree is lost from the tree.