1. Understanding the Problem

You are given the root of a binary tree. Your task is to invert the tree, and then return its root.

What Does "Invert" Mean?

Inverting a binary tree means producing its exact mirror image. For every single node in the tree, you must swap its left child with its right child.

A Quick Example

Imagine a simple tree where the root is 4, its left child is 2, and its right child is 7.

Original Tree:

      4
    /   \
   2     7
            

Inverted Tree:

      4
    /   \
   7     2
            

If the sub-trees (2 and 7) had their own children, you would have to swap those children as well, all the way down to the bottom of the tree.

2. The Core Intuition: The Mirror Effect

Trees are inherently recursive data structures. A tree is just a root node connected to smaller trees (the left sub-tree and the right sub-tree).

Because of this, if we can figure out the logic to swap the children of just one node, we can reuse that exact same logic for every other node in the tree. To create a mirror image, we stand at the top of the tree, grab the left and right branches, and swap them. Then, we travel down the left branch and do the same thing. Then, we travel down the right branch and do it again.

3. The Logic Step-by-Step

We will use a Depth-First Search (DFS) recursive approach. Here is the exact blueprint:

1. The Base Case: If the current node is null (meaning we have reached the bottom of a branch and fallen off), simply return null to stop the process.
2. The Action (Swap): Take the current node's left child and right child, and swap them using a temporary variable.
3. The Recursive Leap: Call this exact same function on the new left child to invert its sub-tree.
4. Call this exact same function on the new right child to invert its sub-tree.
5. Return: Once all recursive calls finish, return the root node of the fully inverted tree.

4. Complexity Analysis

• Time Complexity: O(N) — Where N is the total number of nodes in the tree. We must visit every single node exactly once to swap its children.
• Space Complexity: O(H) — Where H is the height of the tree. This space is used by the recursive call stack. In the worst-case scenario (a completely unbalanced tree that looks like a straight line), the space complexity becomes O(N). In the best case (a perfectly balanced tree), it is O(log N).

5. Code Implementations

Expand the sections below to see the optimal O(N) recursive implementation across different languages.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root):
        # Base case: if the tree is empty, return None
        if not root:
            return None
            
        # Swap the left and right children
        temp = root.left
        root.left = root.right
        root.right = temp
        
        # Recursively invert the left and right sub-trees
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        # Return the original root, which now sits atop an inverted tree
        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Base case: if the tree is empty, return null
        if (root == null) {
            return null;
        }
        
        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert the left and right sub-trees
        invertTree(root.left);
        invertTree(root.right);
        
        // Return the original root
        return root;
    }
}

/**
 * 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) {
        // Base case: if the tree is empty, return nullptr
        if (root == nullptr) {
            return nullptr;
        }
        
        // Swap the left and right children
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        
        // Recursively invert the left and right sub-trees
        invertTree(root->left);
        invertTree(root->right);
        
        // Return the original root
        return root;
    }
};

6. Conclusion: You Are Ready

Congratulations! You have just conquered the problem that stumped veteran engineers. By understanding how to isolate the logic to a single node and leaning on the power of recursion to handle the rest, tree problems become incredibly manageable. Remember the blueprint: establish a base case, define the action for the current node, and make your recursive leaps. Keep practicing, and you will confidently master binary trees!