Invert a Binary Tree in Java: Recursive Approach

Binary trees are fundamental data structures in computer science. Understanding how to manipulate them—such as traversing them or altering their fundamental structure—is crucial for any backend developer. One classic and educational problem is inverting a binary tree.

Simply put, inverting a binary tree means that every node’s left child and right child pointers are swapped with each other, and this swapping process must apply recursively to all subtrees within the main structure.

Understanding the Tree Inversion Problem

The goal is not just to swap the root’s children, but to treat the entire structure as a single unit and mirror it across the vertical axis. If the original tree looked like a letter ‘F’, the inverted tree should look like a mirror-image.

This problem is ideally solved using recursion because the definition of “inversion” is inherently self-referential: to invert a tree, you must invert its subtrees.

The Recursive Solution

The provided Java method demonstrates the most elegant and standard solution to this problem: a depth-first recursive approach. Let’s break down how the logic works line by line.

The implementation is:

public static TreeNode invertBinaryTree(TreeNode root) {
  if (root == null) {
    return null;
  }
  TreeNode leftSubTree = invertBinaryTree(root.right);
  TreeNode rightSubTree = invertBinaryTree(root.left);
  root.left = leftSubTree;
  root.right = rightSubTree;
  return root;
}

When analyzing recursive algorithms, it is critical to identify the base case first. In this function, the base case is when root == null, which stops the recursion and allows the function to safely return null up the call stack.

Step-by-Step Code Walkthrough

1. Base Case Check:if (root == null) { return null; }

   This is the exit condition. If we reach a null pointer (meaning we’ve gone past a leaf node), we simply return null and do nothing further.

2. Recursive Calls (The Swap Preparation):TreeNode leftSubTree = invertBinaryTree(root.right);
TreeNode rightSubTree = invertBinaryTree(root.left);

   Instead of simply swapping the pointers (which would only swap the root’s immediate children), we recursively call the inversion function on the right subtree (which should become the new left) and the left subtree (which should become the new right). Crucially, these calls process and invert the entire subtrees before returning the fully inverted structures.

3. The Swap:root.left = leftSubTree;
root.right = rightSubTree;

   Once the recursive calls have returned the fully processed and inverted subtrees, we perform the actual pointer swap. The inverted right subtree is assigned to the root’s left pointer, and the inverted left subtree is assigned to the root’s right pointer.</li\>

4. Return Value:return root;

   The function returns the modified root node, completing the inversion for that level.

Complexity Analysis

Understanding the time and space complexity confirms that this recursive approach is highly efficient:

• Time Complexity:O(N)

  Where N is the number of nodes in the tree. We visit every single node exactly once to perform the swap, resulting in a linear time complexity relative to the size of the tree.</li\>

• Space Complexity:O(H)

  Where H is the height of the tree. This space is used by the recursion stack. In the best case (a balanced tree), H is log N. In the worst case (a skewed list), H is N.

In conclusion, the method of tree inversion is a perfect demonstration of how recursion allows developers to solve structural problems by breaking them down into smaller, self-similar, and solvable pieces.