LeetCode 226: Invert Binary Tree Using Recursive DFS in C++

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

The Invert Binary Tree problem asks us to transform a binary tree into its mirror image. For every node, the left child must become the right child, and the right child must become the left child.

A recursive depth-first search is a natural fit because a binary tree is composed of smaller binary subtrees. We can solve the entire problem by applying the same operation to the current node and then recursively applying it to both child subtrees.

This article explains:

• How to recognize the recursive tree pattern
• Why swapping only the root's children is insufficient
• How the recursive invariant guarantees correctness
• Why the solution runs in O(n) time
• How recursion depth affects auxiliary space usage

Original Problem and Credit

This article is based on the LeetCode problem “Invert Binary Tree.”

• Original problem: LeetCode 226 — Invert Binary Tree
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem asks us to invert a binary tree and return its root.

Original Problem in Simple Terms

A binary tree node may have:

• A left child
• A right child
• Both children
• No children

To invert the tree, we must swap the left and right children of every node.

For example:

Original:              Inverted:

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

The root remains the same node, but the positions of all left and right subtrees are reversed.

Important constraints:

• The tree contains between 0 and 100 nodes.
• Each node value is between -100 and 100.
• An empty tree is valid and must remain empty.

Real-World Scenario

Imagine a software system that displays a binary workflow hierarchy.

Each workflow step may have two visual branches:

• A left-side branch
• A right-side branch

The dashboard is being adapted for a mirrored display mode. In mirrored mode, every left-side branch must appear on the right, and every right-side branch must appear on the left.

Changing only the top-level branches would not be enough. Every nested workflow step must also exchange its left and right branches.

This scenario is hypothetical, but it is mathematically equivalent to inverting a binary tree:

• Each workflow step is a tree node.
• Its two visual branches are its left and right children.
• Mirroring the entire workflow means swapping the children of every node.
• The node values and parent-child relationships remain unchanged.
• Only the left-versus-right positions change.

Examples

Example 1: Complete Tree

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

At node 4, the subtrees rooted at 2 and 7 exchange positions.

The same operation also occurs inside those subtrees:

• At node 2, nodes 1 and 3 exchange positions.
• At node 7, nodes 6 and 9 exchange positions.

Example 2: Three Nodes

Input:  root = [2,1,3]
Output: [2,3,1]

Original tree:

    2
   / \
  1   3

Inverted tree:

    2
   / \
  3   1

Example 3: Empty Tree

Input:  root = []
Output: []

There are no nodes to process, so the result is also an empty tree.

Edge Example: One Node

Input:  root = [5]
Output: [5]

A single node has no children to exchange. The tree therefore remains unchanged.

Mapping to the Original Problem

The transformation does not create or delete workflow steps. Similarly, the algorithm does not create or delete tree nodes.

It only exchanges each node's two child pointers.

Solution Intuition

The key observation is that a binary tree is recursive.

Each node contains:

1. A value
2. A left subtree
3. A right subtree

The left and right subtrees are themselves binary trees. Therefore, the same inversion operation that applies to the whole tree also applies to each subtree.

For any non-null node, we need to perform three actions:

1. Swap its left and right children.
2. Invert the subtree now stored on the left.
3. Invert the subtree now stored on the right.

When recursion reaches a null pointer, there is no node and no subtree to invert. That gives us the base case.

Why Swapping Only the Root Is Not Enough

Suppose we only exchange the root's two children:

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

The top-level subtrees move, but the nodes inside them are still arranged in their original left-to-right order.

The correct inverted tree must also swap the children of nodes 2 and 7:

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

This is why the operation must be applied recursively at every node.

Why Depth-First Search Fits

Depth-first search explores a branch of a tree before returning to process other branches.

Recursive DFS works well here because:

• Every node must be visited.
• The work performed at each node is small and identical.
• Each child is the root of a smaller instance of the same problem.
• The recursion naturally stops at null child pointers.

We do not need a hash map, stack object, queue, or additional tree.

Algorithm

1. If root is nullptr, return nullptr.
2. Store one child pointer temporarily.
3. Exchange root->left and root->right.
4. Recursively invert the subtree now referenced by root->left.
5. Recursively invert the subtree now referenced by root->right.
6. Return root.

The function modifies the existing tree in place.

Why the Algorithm Works

We can prove correctness using a recursive invariant.

Invariant

After invertTree(node) finishes, the subtree rooted at node is the exact mirror image of the subtree that was rooted at node before the call.

Base Case

If node is nullptr, the subtree is empty.

The mirror image of an empty tree is also an empty tree, so returning nullptr is correct.

Recursive Case

Assume node is not null.

The algorithm first exchanges the node's original left and right child pointers. This correctly mirrors the immediate child positions of the current node.

It then recursively inverts both child subtrees.

By the recursive assumption:

• The new left subtree becomes the mirror image of the original right subtree.
• The new right subtree becomes the mirror image of the original left subtree.

Therefore, the entire subtree rooted at the current node becomes the exact mirror image of its original form.

Since the property holds for the base case and is preserved at every non-null node, the algorithm correctly inverts the entire tree.

Complexity Analysis

Let n be the number of nodes in the binary tree, and let h be the tree's height.

Time Complexity

Each node is visited exactly once.

At each node, the algorithm performs constant-time work:

• One null check
• A constant number of pointer assignments
• Two recursive calls

The recursive calls collectively process each descendant once. Therefore, the total time complexity is:

O(n)

The algorithm cannot asymptotically do better than O(n) because every node may need its children exchanged.

Space Complexity

The tree is modified in place, so the pointer swapping itself uses only:

O(1)

additional local storage per active function call.

However, recursive calls use the program's call stack. The maximum number of simultaneously active calls is proportional to the tree height:

O(h)

Therefore, the auxiliary space complexity is:

O(h)

This becomes:

• O(log n) for a balanced binary tree
• O(n) for a completely skewed binary tree

The worst-case auxiliary space complexity is therefore O(n).

Corrected Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode* left;
 *     TreeNode* right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(
 *         int x,
 *         TreeNode* left,
 *         TreeNode* right
 *     ) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        TreeNode* temporary = root->left;
        root->left = root->right;
        root->right = temporary;

        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

How the Code Works

The base case handles an empty subtree:

if (root == nullptr) {
    return nullptr;
}

Without this check, the code would attempt to access root->left or root->right through a null pointer.

The next three lines exchange the child pointers:

TreeNode* temporary = root->left;
root->left = root->right;
root->right = temporary;

temporary must be a pointer because both root->left and root->right have type TreeNode*.

After the current node's children are exchanged, the function recursively processes both subtrees:

invertTree(root->left);
invertTree(root->right);

Finally, the function returns the root of the inverted subtree:

return root;

At the original call, this is the root of the fully inverted tree.

Walkthrough

Consider:

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

Initial tree:

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

Step 1: Process Node 4

Exchange its children:

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

The root's immediate children are now correct, but the two subtrees still need to be inverted.

Step 2: Process Node 7

Node 7 is now the left child of 4.

Exchange its children:

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

The recursive calls then reach nodes 9 and 6.

Both are leaves, so their left and right pointers are both null. Exchanging two null pointers makes no visible change.

Step 3: Process Node 2

Node 2 is now the right child of 4.

Exchange its children:

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

The recursive calls then process leaf nodes 3 and 1.

Step 4: Return Through the Recursive Calls

Every subtree has now been inverted, so each recursive call returns its subtree root.

The original call returns node 4.

Final level-order representation:

[4,7,2,9,6,3,1]

Common Mistakes

1. Swapping Only the Root's Children

Exchanging only root->left and root->right mirrors one level, not the entire tree.

Every descendant node must also be processed.

2. Missing the Null Base Case

Code such as this is unsafe when root is null:

root->left = root->right;

Always check for nullptr before accessing node members.

3. Using References Instead of Child Pointers Incorrectly

The child members have type TreeNode*, not TreeNode.

This is incorrect:

TreeNode& temporary = root->left;

root->left is a pointer, so the temporary variable must also be a pointer:

TreeNode* temporary = root->left;

4. Losing One Subtree During Assignment

This does not correctly swap the pointers:

root->left = root->right;
root->right = root->left;

After the first line, the original left pointer has been overwritten. Both child pointers may then refer to the original right subtree.

Use a temporary variable or std::swap.

5. Forgetting to Recurse

A local swap changes only one node's child positions. The recursive calls are what apply the transformation to the entire tree.

6. Reporting O(1) Total Space

The tree is modified in place, but recursive calls consume call-stack space.

The correct auxiliary space complexity is O(h), where h is the tree height.

Key Takeaways

• A binary tree is recursive because each child is the root of another binary tree.
• Inverting a tree requires swapping the left and right children of every node.
• Recursive DFS is appropriate when the same operation must be applied to every subtree.
• The null pointer is the natural recursion base case.
• The algorithm runs in O(n) time and uses O(h) auxiliary stack space.
• In-place modification does not imply O(1) total auxiliary space when recursion is involved.