Introduction & Problem Explanation

The Invert Binary Tree problem (sometimes famously known as mirroring a binary tree) asks us to take the root of a binary tree and invert it, so that for every node in the tree, its left and right subtrees are swapped.

For example, if the input tree is: 

             4
           /   \
          2     7
         / \   / \
        1   3 6   9
The inverted output tree should be: 
             4
           /   \
          7     2
         / \   / \
        9   6 3   1
This is a classic recursive tree problem that tests understanding of tree traversals and structural modifications.

Illustration of mirroring/inverting a binary tree in Java
Real-World Analogy: The Ceiling Mobile Decoration

Imagine a decorative mobile hanging from the ceiling. It has a main central branch, which splits into two smaller branches (left and right), each holding further sub-decorations. If you look at it in a mirror, or if you grab the main branch and spin it 180 degrees, every single left-hand decoration swaps positions with the right-hand decoration. To perform this swap in code, you start at the top, swap the two main branches, and then go down to each sub-branch and swap their hangers, repeating this all the way down to the individual hanging charms (leaf nodes).

The Algorithmic Approach

1. Recursive Depth-First Search (O(n) Time, O(h) Space)

A binary tree has a naturally recursive structure, making recursion the most elegant way to solve this. As we traverse the tree (post-order DFS):

  • If the current node is null, we reach a base case and simply return null.
  • We recursively call our invert function on the left child: invertTree(root.left).
  • We recursively call our invert function on the right child: invertTree(root.right).
  • We swap the left and right pointers of the current node: TreeNode temp = root.left; root.left = root.right; root.right = temp;.
  • We return the root node.
This visits every node exactly once, giving a time complexity of O(n). The space complexity is O(h), where h is the height of the tree, representing the recursion stack depth.

Step-by-Step Execution Walkthrough

Let's trace the recursive inversion on a simple binary tree:

            4
           / \
          2   7
  1. Step 1 (Root call): Start at root node 4.
    • We must invert its left subtree (node 2) and right subtree (node 7) first.
  2. Step 2 (Invert Left child 2): Travel to node 2.
    • Node 2 has no children (left and right are null).
    • Recursive calls on left and right return null. No swap is needed (or swapping nulls does nothing).
    • Node 2 returns itself back to node 4.
  3. Step 3 (Invert Right child 7): Travel to node 7.
    • Node 7 has no children.
    • Recursive calls return null.
    • Node 7 returns itself back to node 4.
  4. Step 4 (Swap at Root 4):
    • We are back at node 4. We swap its left pointer (currently node 2) and right pointer (currently node 7).
    • After swapping: 4's left becomes node 7, and 4's right becomes node 2.
    • The tree structure is now: 
                          4
                   / \
                  7   2
  5. Step 5 (Completion): The root node 4 is returned, and the tree is successfully inverted.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (root == null) return null;: The base case. An empty tree or empty child pointer has nothing to invert, so we return null.
  • TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right);: Recursively solves the sub-problems, ensuring that we mirror all lower subtrees before linking them back.
  • root.left = right; root.right = left;: The pointer swapping step, placing the mirrored right subtree in the left branch and vice versa.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class InvertBinaryTree {

    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    // Optimized - Recursive - O(n)
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public static void main(String[] args) {
        InvertBinaryTree solver = new InvertBinaryTree();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);

        System.out.println("--- Invert Binary Tree Demonstration ---");
        System.out.println("Root left before invert: " + root.left.val);
        solver.invertTree(root);
        System.out.println("Root left after invert: " + root.left.val);
    }
}

Conclusion

Solving the Invert Binary Tree problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.