Problem Overview

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

Inverting a binary tree means swapping the left and right child of every node in the tree.

Example 1

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

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

Explanation:
Every left child is swapped with its corresponding right child recursively throughout the entire tree.

Example 2

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

Example 3

Input: root = []
Output: []

---

Intuition / Approach

The problem can be understood visually — at each node in the binary tree, we swap its left and right children. Then we repeat the same process for the left and right subtrees.

There are multiple ways to perform this inversion:

1. Recursive (Depth-First Search) approach.
2. Iterative (Breadth-First Search) approach using a queue.

The recursive approach is the most intuitive and elegant because it mirrors the tree’s structure directly.

---

Algorithm Explanation (Recursive Approach)

We define a recursive function invertTree(root) that:

1. Returns null if the current node (root) is null.
2. Swaps the left and right child nodes.
3. Recursively inverts the left and right subtrees.
4. Returns the root node after the swap.

Step-by-step explanation:

1. Base Case:
   If the node is null, there’s nothing to invert, so we simply return null.
2. Swap Operation:
   Swap root.left and root.right.
3. Recursive Calls:
   Call the same function on both root.left and root.right to invert their subtrees.
4. Return Result:
   Return the modified root node.

---

Java Code Implementation (Recursive Approach)

// Definition for a binary tree node
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class InvertBinaryTree {

    public TreeNode invertTree(TreeNode root) {
        // Base case: if the node is null, nothing to invert
        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 subtrees
        invertTree(root.left);
        invertTree(root.right);

        // Return the root after inversion
        return root;
    }

    // Example usage
    public static void main(String[] args) {
        InvertBinaryTree tree = new InvertBinaryTree();

        // Construct sample binary tree
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        TreeNode invertedRoot = tree.invertTree(root);
        tree.printTree(invertedRoot); // Optional method to visualize result
    }

    // Helper method to print tree in-order
    private void printTree(TreeNode root) {
        if (root == null) return;
        printTree(root.left);
        System.out.print(root.val + " ");
        printTree(root.right);
    }
}

---

Complexity Analysis

1. Time Complexity:O(n)
   • Every node in the binary tree is visited exactly once.
   • Swapping children takes constant time per node.
   • Hence, total time complexity = O(n), where n is the number of nodes.
2. Space Complexity:O(h)
   • The recursion depth depends on the height of the binary tree (h).
   • In the worst case (skewed tree), recursion depth can be O(n).
   • In the best case (balanced tree), depth is O(log n).

---

Alternative Approach (Iterative using Queue)

If you want to avoid recursion (for example, to prevent stack overflow in deep trees), you can use an iterative level-order traversal using a queue.

At each step:

1. Dequeue a node from the queue.
2. Swap its left and right children.
3. Enqueue the non-null children for further processing.

Java Implementation:

import java.util.LinkedList;
import java.util.Queue;

public class InvertBinaryTreeIterative {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();

            // Swap the children
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;

            // Add children to the queue if not null
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }

        return root;
    }
}

---

Comparison Between Recursive and Iterative Approaches

Criteria	Recursive Approach	Iterative Approach
Ease of Implementation	Easier and cleaner	Slightly more code
Space Usage	O(h) (due to recursion)	O(n) (due to queue)
Performance	O(n) time	O(n) time
Best for	Balanced trees	Deep or skewed trees