Invert Binary Tree

Swap the left and right children at every node.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Invert Binary Tree: Postorder recursion returns inverted child subtrees, then the parent assigns old right to left and old left to right.

Input and goalSwap the left and right children at every node.

Start with the original linksFor tree [4,2,7,1,3,6,9], call invert_tree(4). The root currently links left to 2 and right to 7.

• 4call invert(4)
  • 2
    • 1
    • 3
  • 7
    • 6
    • 9

callStack[4]links4.left=2; 4.right=7

Recognize it

Use this pattern when every node applies the same local child-pointer transformation and the parent needs transformed child roots returned from recursion.

Keep true

invert_tree(node) returns the same node object after every edge in its subtree is mirrored: its new left is the fully inverted old right and its new right is the fully inverted old left.

Reuse it

For recursive structural edits, first obtain transformed child roots, then reconnect them locally and return the current root; this transfers to pruning, flattening, and persistent tree rewrites.

Pattern: Tree DFS.

Simple idea: Invert both child trees, then place the old right result on the left and the old left result on the right.

def invert_tree(root: TreeNode | None) -> TreeNode | None:
   if root is None:
      return None
   root.left, root.right = invert_tree(root.right), invert_tree(root.left)
   return root

Cost: $O(n)$ time and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.