Invert Binary Tree — DSA

Problem

Given the root of a binary tree, invert the tree (mirror it left-to-right) and return its root.

Inverting means that for every node, its left and right children are swapped. The result is the tree's mirror image: a node that was the leftmost leaf becomes the rightmost leaf, and so on.

      4                 4
    /   \             /   \
   2     7    →      7     2
  / \   / \         / \   / \
 1   3 6   9       9   6 3   1

The tree can be empty (root = null). Return null in that case.
Modify the tree in place. Returning the same root reference is expected.

Examples

Example 1

Input: root = [4,2,7,1,3,6,9]

Output: [4,7,2,9,6,3,1]

Constraints

•The number of nodes in the tree is in the range [0, 100].

Hints

Hint 1

Swap left and right children, then recursively invert each subtree — this works top-down, bottom-up, or level-by-level; the ORDER doesn't matter, only that every node's children eventually get swapped.

Hint 2

An iterative BFS version swaps children level by level instead of recursively — useful to know as a 'can you do it without recursion' follow-up.

Solutions

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    // Swap children
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    // Recurse
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

Time: O(n) · Space: O(h) where h = tree height