Invert Binary Tree

Tags

Invert Binary Tree

Category

Binary Trees

Difficulty

Easy

Problem Statement

Given a binary tree, invert it by swapping every node's left and right children. The inversion should be performed in place and the root of the inverted tree should be returned.

Intuition

Inverting a binary tree means creating its mirror image. At every node, the left subtree becomes the right subtree and vice versa. If we recursively swap children at every node, the entire tree becomes mirrored. The order of traversal does not matter — pre-order, post-order, or even BFS all work, as long as every node's children get swapped.

Approach

  1. If the node is null, return (base case).
  2. Swap the node's left and right children.
  3. Recursively invert the left subtree.
  4. Recursively invert the right subtree.
  5. Return the node.

Alternatively, use an iterative BFS with a queue: for each node dequeued, swap its children and enqueue the non-null children.

Pseudocode

function invertBinaryTree(node):
    if node is null:
        return null
    swap(node.left, node.right)
    invertBinaryTree(node.left)
    invertBinaryTree(node.right)
    return node

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Every node is visited once.
  • Space: O(h) where h is the height of the tree for the recursive approach (call stack). O(n) in the worst case for an iterative BFS approach (queue size at the widest level).

Key Insights

  • Swapping can happen before or after the recursive calls — both produce the correct result.
  • The operation is its own inverse: inverting an already-inverted tree restores the original.
  • This is one of the simplest tree transformations and a great introduction to recursive tree manipulation.
  • An iterative approach using a queue (BFS) is equally valid and avoids potential stack overflow.

Edge Cases

  • Null/empty tree: return null.
  • Single node (no children): the tree is its own mirror; return the node unchanged.
  • Completely left-skewed tree becomes completely right-skewed, and vice versa.
  • A symmetric tree (mirror of itself) remains unchanged after inversion.

Linked mentions