Crack the Backend

Problem Statement

Given the root of a binary tree, invert the tree and return its root. Inverting means: for every node, we swap its left and right child subtrees. So the left subtree becomes the right and the right becomes the left (mirror image).

We can do this in place by swapping the left and right pointers at each node. Recursively: swap the two children of the root, then invert the left subtree and the right subtree. Base: if root is null, return null.

Key Observations

At each node: swap root.left and root.right (using a temporary variable). Then recursively invert root.left and root.right. The order of the two recursive calls does not matter since we already swapped; we are inverting the (new) left and right subtrees.
Iterative: use a queue (or stack), push the root; while not empty, pop a node, swap its children, push non-null children. Same idea.

Approach

High-level: If root == null return null. Swap root.left and root.right. Call invertTree(root.left) and invertTree(root.right). Return root.

Steps:

if root == null return null. TreeNode tmp = root.left; root.left = root.right; root.right = tmp.
invertTree(root.left); invertTree(root.right). return root.

Implementation

Java

public TreeNode invertTree(TreeNode root) {

    if (root == null) {
        return null;
    }

    TreeNode t = root.left;
    root.left = root.right;
    root.right = t;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

Test Cases

Example 1

Input

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

Expected

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

Explanation

Left and right swapped at every node.

Complexity Analysis

Time: O(n).
Space: O(h).

Follow-ups

Iterative (BFS/DFS with stack or queue).