Module 17 · Binary Trees: Recursive DFS and Structural Contracts

167. Invert Binary Tree

Bridge · Download this solution · All solutions and shared helpers

Problem

Invert a binary tree in place and return its original root object. Every node's left and right subtrees exchange sides recursively. None remains None. Node values and node identities must be preserved.

Examples

Example 1

tree_values(invert_tree(build_tree([1,2,3,4])))
=> [1, 3, 2, None, None, None, 4]

The deeper left child also changes side.

Example 2

invert_tree(None)
=> None

An empty subtree stays empty.

Example 3

root=build_tree([7])
(invert_tree(root) is root, tree_values(root))
=> (True, [7])

A singleton keeps its identity and shape.

Reveal the worked solution and reasoning

Why this mechanism works

The helper promises the mirror of one entire subtree. First obtain the mirrored old left and old right subtrees, then attach them on opposite sides. Saving both results in separate variables makes ownership explicit and prevents an overwritten pointer from being read as though it were still the original child.

State and boundaries

left and right are completed mirrors of the original child subtrees. The current root object is reused.

Protocol

Return None for an absent node.
Invert the old left subtree.
Invert the old right subtree.
Attach mirrored right as left and mirrored left as right.
Return the current node.

Visualization

before: 1(left=2,right=3)
mirror children: 2 and 3
after:  1(left=3,right=2)
the root object is unchanged

Python implementation

from structures import build_tree, tree_values

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

tree_values(invert_tree(build_tree([1,2,3,4])))

L4 invert_tree: if root is None:
root=N1(val=1,left=N2,right=N3)

L4 invert_tree: if root is None:
root=N2(val=2,left=N4,right=None)

L4 invert_tree: if root is None:
root=N4(val=4,left=None,right=None)

L4 invert_tree: if root is None:
root=None

L6 invert_tree: left = invert_tree(root.left)
root=N4(val=4,left=None,right=None); left=None

L4 invert_tree: if root is None:
root=None

L7 invert_tree: right = invert_tree(root.right)
root=N4(val=4,left=None,right=None); left=None; right=None

L6 invert_tree: left = invert_tree(root.left)
root=N2(val=2,left=N4,right=None); left=N4(val=4,left=None,right=None)

... 7 intermediate state changes omitted ...

L4 invert_tree: if root is None:
root=None

L7 invert_tree: right = invert_tree(root.right)
root=N3(val=3,left=None,right=None); left=None; right=None

L7 invert_tree: right = invert_tree(root.right)
root=N1(val=1,left=N2,right=N3); left=N2(val=2,left=None,right=N4); right=N3(val=3,left=None,right=None)

L8 invert_tree: root.left, root.right = right, left
root=N1(val=1,left=N3,right=N2); left=N2(val=2,left=None,right=N4); right=N3(val=3,left=None,right=None)

Result: [1, 3, 2, None, None, None, 4]. The deeper left child also changes side.

invert_tree(None)

L4 invert_tree: if root is None:
root=None

Result: None. An empty subtree stays empty.

Why the solution is correct

An empty tree is its own mirror. By the child-call contract, both returned subtrees are already mirrored; exchanging their sides around the unchanged root produces precisely the mirror of the original tree. Structural induction covers all nodes without allocating replacements.

Time and space

O(n) time and O(h) recursive stack space; mutation reuses all existing nodes.

Common mistakes

Sequential assignments that read root.left after overwriting it can attach the same subtree twice. Reversing values alone does not mirror the structure.

Reasoning card

State: left and right are completed mirrors of the original child subtrees. The current root object is reused.

Invariant: Returned subtree is the mirror of the original subtree.

Decision to rehearse: Invert child subtrees, then attach them on opposite sides.

Finish: Return the current node

Transfer exercise

Prove that inverting twice restores every original pointer relationship, then use that property in a test.