Invert Binary Tree Solution Explained

Data Structures / Tree

Invert Binary Tree

Easy

Given the root of a binary tree, invert the tree and return its root.

Inverting a binary tree means swapping every left node with its corresponding right node at every level of the tree. This famous problem is often cited as a fundamental exercise in tree recursion.

Example

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Original Tree:

      4
     / \
    2   7
   / \ / \
  1  3 6  9

Inverted Tree:

      4
     / \
    7   2
   / \ / \
  9  6 3  1

Explanation: Every left child becomes the right child, and every right child becomes the left child.

Understanding the Problem

Inverting a binary tree means creating a mirror image of the tree. For every node in the tree, its left and right children are swapped.

Key observations:

An empty tree (null root) remains empty when inverted
A tree with only the root node remains the same
The inversion happens locally at each node — we just swap left and right children
We need to invert all subtrees recursively to get the complete inverted tree

This problem is a perfect example of tree recursion because the same operation (swap children) applies to every node in the tree.

Recursive Approach

The recursive solution is elegantly simple:

Base case: If the node is null, return null (nothing to invert)
Swap: Exchange the left and right child pointers of the current node
Recurse left: Invert the left subtree (which was originally the right)
Recurse right: Invert the right subtree (which was originally the left)
Return: Return the root of the inverted tree

The beauty of this approach is that the recursion handles all levels automatically. Each node only needs to worry about swapping its own children — the recursive calls take care of the rest.

Idea Map

Start at Root

If node == null: return null

Swap left and right children

Recursively invert left subtree

Recursively invert right subtree

Return root

Inverted Tree Complete

Complexity Analysis

Time Complexity

O(n) - We visit each node exactly once to swap its children, where n is the number of nodes.

Space Complexity

O(h) - Call stack depth equals tree height h. Worst case O(n) for skewed tree, O(log n) for balanced tree.

Code


def invertTree(root):
Initializes the function `invertTree` which takes the `root` of a binary tree as input.
    if not root:
Base case: if the root is None (null), we have an empty tree - nothing to invert.
        return None
Return None for empty tree (no nodes to invert).
    root.left, root.right = root.right, root.left
Swap the left and right children using Python's tuple unpacking. This is done in-place.
    invertTree(root.left)
Recursively invert the left subtree (which was originally the right subtree).
    invertTree(root.right)
Recursively invert the right subtree (which was originally the left subtree).
    return root
Return the root of the inverted tree. The root itself doesn't change, only its children.


public TreeNode invertTree(TreeNode root) {
Initializes the function `invertTree` which takes the `root` of a binary tree as input.
    if (root == null) {
Base case: if the root is null, we have an empty tree.
        return null;
Return null for empty tree (no nodes to invert).
    }
End of the base case check.
    TreeNode temp = root.left;
Store left child in a temporary variable before swapping.
    root.left = root.right;
Assign right child to left pointer.
    root.right = temp;
Assign stored left child to right pointer. Swap complete!
    invertTree(root.left);
Recursively invert the left subtree.
    invertTree(root.right);
Recursively invert the right subtree.
    return root;
Return the root of the inverted tree.
}
End of the function.


TreeNode* invertTree(TreeNode* root) {
Initializes the function `invertTree` which takes a pointer to the `root` of a binary tree.
    if (root == nullptr) {
Base case: if the root is nullptr, we have an empty tree.
        return nullptr;
Return nullptr for empty tree (no nodes to invert).
    }
End of the base case check.
    TreeNode* temp = root->left;
Store left child in a temporary variable using arrow operator.
    root->left = root->right;
Assign right child to left pointer using arrow operator.
    root->right = temp;
Assign stored left child to right pointer. Swap complete!
    invertTree(root->left);
Recursively invert the left subtree.
    invertTree(root->right);
Recursively invert the right subtree.
    return root;
Return the root pointer of the inverted tree.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Forgetting the base case

Always check if the node is null first. Without this base case, you'll get a null pointer exception when trying to access node.left or node.right.

💡

Forgetting to recurse on subtrees

Swapping at the root only isn't enough! You must recursively invert all subtrees. Each node's children need to be swapped, not just the root's.

✓

Using a temporary variable for swap

In Java and C++, use a temporary variable to swap children. Python allows tuple unpacking: a, b = b, a. This is a classic swap pattern!

Want to Master Tree Recursion?

Tree recursion is a fundamental pattern that appears in many tree problems. Understanding how to traverse and manipulate trees recursively will help you solve a wide variety of problems.

Learn more about tree recursion →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Invert Binary Tree' problem on LeetCode.

AlgoExplained.dev