Invert Binary Tree

Problem Link

Problem: Invert Binary Tree

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Inversion means swapping every left and right subtree recursively.

Examples

Example 1

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

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

Example 2

Input: root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 100]
-100 <= Node.val <= 100

Intuition

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

This problem is a classic example of post-order traversal (process children before the node).

We can solve it using either:

Recursion (Elegant and concise)
Iteration with a queue (BFS)

Approach 1: Recursive (Post-Order)

Algorithm

If root is null → return null
Recursively invert left and right subtrees
Swap left and right pointers
Return the root

Code (Java)

class Solution {
    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;
    }
}

Approach 2: Iterative (Level Order using Queue)

Algorithm

Use a queue for level-order traversal.
At each node, swap its left and right child.
Add the children (if not null) to the queue.

Code (Java)

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

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

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

            // Swap left and right
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;

            if (current.left != null) q.add(current.left);
            if (current.right != null) q.add(current.right);
        }

        return root;
    }
}

Time and Space Complexity

For both approaches:

Time Complexity: O(N)
Every node is visited exactly once.
Space Complexity:
- Recursive: O(H) (recursion stack, H is height of tree)
- Iterative: O(W) (queue stores one level = max width)

Dry Run (Recursive)

Input:

       1
     /   \
    2     3

Recursive call flow:

invertTree(1)
- invertTree(2) → returns node with left = null, right = null
- invertTree(3) → returns node with left = null, right = null
- swap → left = 3, right = 2
  → Output: 1 → left: 3, right: 2

Conclusion

This is a fundamental tree manipulation problem.
Ideal for understanding recursion, post-order traversal, and structural transformation of trees.
Preferred method: recursion (simpler and readable).