Invert/Mirror Binary Tree: swap left and right recursively

• Invert Binary Tree produces the mirror image of a tree by swapping the left and right child at every node.
• Recursive traversal visits each node, performs a constant-time swap, and recurses into both children.
• Order independence means you can swap first then recurse, or recurse first then swap, with identical results.
• In-place mutation modifies the original tree; a non-destructive variant builds a new mirrored tree.
• Time is O(n) for one visit per node; space is O(h) for the call stack.

What is the Invert Binary Tree problem?

Inverting a binary tree means swapping the left and right child of every node so the tree becomes its own mirror image. This is a transformation rather than a query: instead of returning a measurement, you mutate the structure. It is famously one of the simplest tree problems and is often used to test understanding of recursion.

package com.bank.service;

public class HierarchyMirrorService {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // Swap children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // Recurse into both subtrees
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Why does this problem matter in banking systems?

At the National Bank of India, the approval hierarchy stores primary approvers on the left and backup approvers on the right. During a disaster-recovery drill, the system needs the mirror version where backups become primary at every level. The recursive swap flips the entire chain consistently, and the mirrored tree is persisted as a drill snapshot so operations can validate that backup approvers are correctly wired before a real failover.

How does the recursion work internally?

The base case is a null node, which has nothing to invert, so you return null. For a non-null node, you swap its left and right children using a temporary variable, then recursively invert both the (now-swapped) left subtree and the right subtree.

// Step-by-step trace:
//  Before:      4            After:       4
//              / \                        / \
//             2    7                     7    2
//            / \  / \                   / \  / \
//           1  3 6   9                 9  6 3   1
//
// invertTree(4): swap 2,7 → left=7, right=2
//   invertTree(7): swap 6,9 → left=9, right=6
//     invertTree(9): leaf, swap null,null → no change
//     invertTree(6): leaf, swap null,null → no change
//   invertTree(2): swap 1,3 → left=3, right=1
//     invertTree(3): leaf
//     invertTree(1): leaf

Before: [4, 2, 7, 1, 3, 6, 9]
After:  [4, 7, 2, 9, 6, 3, 1]

Why does the swap order not matter?

The swap at a node is independent of the swaps deeper down. Whether you swap first then recurse, or recurse first then swap, every node ends up performing exactly one swap and the final tree is identical. This is because swapping children at one level does not affect the relative arrangement of grandchildren after they are swapped at their own level.

// Variant 1: swap first, then recurse (pre-order)
public TreeNode invertPreOrder(TreeNode root) {
    if (root == null) return null;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertPreOrder(root.left);
    invertPreOrder(root.right);
    return root;
}

// Variant 2: recurse first, then swap (post-order)
public TreeNode invertPostOrder(TreeNode root) {
    if (root == null) return null;
    invertPostOrder(root.left);
    invertPostOrder(root.right);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    return root;
}

// Both produce the exact same result

How is this different from Symmetric Tree check?

Invert Tree is a mutation that produces the mirror. Symmetric Tree is a query that checks if a tree is already its own mirror. After inverting a symmetric tree, the result is the same tree.

| Aspect | Invert Tree | Symmetric Tree |
|--------|------------|----------------|
| Operation | Mutation (transforms) | Query (returns boolean) |
| Result | Modified tree | true or false |
| Changes structure | Yes | No |
| A symmetric tree | Stays the same after invert | Returns true |

What are edge cases?

• Null tree: returns null, nothing to invert.
• Single node: returns the same node, swapping null children changes nothing.
• Already symmetric tree: after inversion, it looks the same.
• Skewed tree (all left): becomes all right after inversion.

// Edge case: skewed tree
// Before:  1        After:  1
//         /                  \
//        2                    2
//       /                      \
//      3                        3
// Left-skewed becomes right-skewed

What are common mistakes?

The most common mistake is writing root.left = root.right; root.right = root.left; without a temporary variable. The first assignment overwrites root.left, so the second assignment copies the new value of root.left (which is the old root.right) back into root.right, making both children the same.

// WRONG: no temporary variable
root.left = root.right;   // left is now old-right
root.right = root.left;   // right is ALSO old-right!

// CORRECT: use a temp
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

What about an iterative approach?

You can use a queue or stack to visit each node and swap its children without recursion. This avoids the stack overflow risk on very deep trees.

public TreeNode invertTreeIterative(TreeNode root) {
    if (root == null) return null;
    java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return root;
}

What about building a new tree instead of mutating?

If the caller still needs the original tree, you should build a new inverted tree rather than mutating the original. The recursive structure is the same, but you create new nodes instead of swapping pointers.

public TreeNode invertNewTree(TreeNode root) {
    if (root == null) return null;
    TreeNode newNode = new TreeNode(root.val);
    newNode.left = invertNewTree(root.right);  // mirror: right becomes left
    newNode.right = invertNewTree(root.left);   // mirror: left becomes right
    return newNode;
}

What should a senior engineer know?

Inverting a BST destroys the BST property: the inverted tree has values in reverse order. If you rely on BST operations after inversion, you need a comparator reversal or a separate structure. Also, inverting twice restores the original tree, since it is its own inverse.

For production disaster-recovery at the National Bank of India, Rajesh persists the inverted tree as a separate snapshot rather than mutating the live hierarchy, so both the primary and backup structures are available simultaneously during the drill.