Difficulty: EasyTrees

Invert Binary Tree

Problem in Plain English

Given the root of a binary tree, swap every left and right child so the tree becomes its mirror image, then return the root. An empty tree stays empty.

Problem Statement

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

Inverting means swapping the left and right child of every node, which mirrors the whole tree. An empty tree inverts to itself.

Constraints

The number of nodes is between 0 and 100, inclusive.
Each node value is between -100 and 100, inclusive; inversion changes child links, not values.

Examples

Example 1

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

Root 4 trades children 2 and 7. Within those moved subtrees, 7 trades 6 and 9, and 2 trades 1 and 3. The leaves have no children, so their values stay unchanged while every left/right path reverses.

Example 2

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

Only root 2 has children to exchange. Nodes 1 and 3 stay childless, so swapping the root already completes this mirror.

Example 3

Input: root = []
Output: []

The root is null. Both approaches return null immediately without allocating or swapping anything.

Example 4

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

The missing right child of root 1 becomes its missing left child. Node 2 moves to the right and swaps its own children from 3,4 to 4,3. This is a structural mirror with null positions retained, not a reversal of the level-order array.

Example 5

Input: root = [8]
Output: [8]

Swapping two null child references leaves a singleton unchanged in value and shape. The in-place approach returns this same node; the copy approach returns a different node holding 8.

Intuition

Mirroring reverses every left/right choice along a root-to-node path. Swapping only the root moves whole subtrees but leaves their interiors facing the old direction. In Example 1, root 4 trades 2 and 7, then node 7 must also trade 6 and 9 and node 2 must trade 1 and 3. The same local operation applies independently at every node. We can either create a separate mirror with fresh nodes or rewire the original nodes; the in-place version returns the original root.

Approaches

Build Mirrored Copy

Solution Details

Reveal Build Mirrored Copy: intuition, complexity, and code

Intuition

Create a fresh node for each original node, copying its value and attaching the mirror of the original right subtree on the left and the mirror of the original left subtree on the right. This builds the correct mirror while preserving the input tree, at the cost of a second tree with n fresh nodes.

Step-by-Step Logic

For any nonempty subtree, allocate a new node with the same value; return null for an empty subtree. In Example 1 begin with a fresh 4, whose two child pointers are initially null.
Fill the new left child by recursively copying and mirroring the original right subtree. Original 7 becomes fresh 7; its left child comes from original 9 and its right child from original 6, yielding [7,9,6].
Fill the new right child by copying and mirroring the original left subtree. Original 2 becomes fresh 2 with fresh children 3 and 1, yielding [2,3,1].
A leaf creates one childless copy after both empty-child calls return null. Once both child results have been attached, return the fresh subtree root; fresh 4 now holds [4,7,2,9,6,3,1] and original 4 remains unchanged.

Why It Works

Induct on subtree size. The mirror of an empty subtree is empty, so returning null is correct. For a nonempty subtree, a fresh root preserves the value. By induction, the two recursive calls return exact mirrors of the original right and left subtrees. Attaching them on opposite sides reverses the first path choice, while the recursive mirrors reverse every remaining path choice. This is precisely the full mirror. Each original node is visited once and produces one distinct fresh node; only those copies are written, so the result shares no nodes with the unchanged input.

Dry Run

Build Mirrored Copy: variable states at each step
Event in execution order	Active original nodes	New-node references (prime means fresh identity)	Returned subtree
Enter 4; allocate 4′, descend original right 7	[4,7]	4′.left = null; 4′.right = null	pending
Allocate 7′, descend original right 9	[4,7,9]	7′.left = null; 7′.right = null	pending
Allocate 9′; both null calls return	[4,7]	9′ children null; 7′.left: null → 9′	9′
Descend original left 6; allocate leaf 6′	[4,7,6] then [4,7]	6′ children null; 7′.right: null → 6′	6′
Complete 7 and attach to 4′	[4]	4′.left: null → 7′; right still null	[7,9,6] using copies
Descend original left 2; allocate 2′ and enter 3	[4,2,3]	2′.left = null; 2′.right = null	pending
Allocate leaf 3′; both null calls return	[4,2]	2′.left: null → 3′	3′
Enter original 1; allocate leaf 1′ and return	[4,2]	2′.right: null → 1′	1′
Complete 2 and attach to 4′	[4]	4′.right: null → 2′	[2,3,1] using copies
Return 4′	[]	fresh 4 with fresh 7 and fresh 2	[4,7,2,9,6,3,1]; input unchanged

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the node count and h the height. Each original node causes one allocation and two child calls, giving O(n) time. The returned mirror itself occupies O(n) new nodes; recursive calls add O(h) auxiliary stack space. Counting the allocated output gives O(n) total additional space, whereas excluding output leaves O(h) auxiliary space. The original tree is retained unchanged and shares no nodes with the result. The valid depth is at most 100, so these recursive snippets run under default language stack limits; an empty input takes constant time and space.

Code

Solution.java

1class TreeNode {2    int val;3    TreeNode left, right;4    TreeNode(int val) { this.val = val; }5}6
7class Solution {8    public TreeNode invertTree(TreeNode root) {9        if (root == null) return null;10        TreeNode copy = new TreeNode(root.val);11        // Copy from opposite sides; never assign into an original node.12        copy.left = invertTree(root.right);13        copy.right = invertTree(root.left);14        return copy;15    }16}

Hints

Hint 1

At one node, which two references must exchange positions to reverse its immediate left/right choice?

Hint 2

Moving a subtree to the other side does not mirror its interior. Apply the same operation to both child subtrees.

Hint 3

For in-place inversion, save the old left child before overwriting it, recurse into each moved child exactly once, and return the current node.

Edge Cases

An empty tree returns null; no new node is created.
A singleton keeps its value and null children; the copy approach creates a fresh identity while in-place inversion retains the original.
A left-only or right-only chain moves to the opposite side at every level, including all 100 nodes at the stated maximum.
Asymmetric trees must mirror missing children too: Example 4 has a null left child after inversion.
Duplicate and negative values must be preserved; values cannot identify nodes or determine which subtree to swap.
In-place inversion is an involution: running it twice restores all original child references. Copying preserves the input, and every call produces a separate output tree.

Common Mistakes and Interview Tips

Assigning left = right before saving old left, then assigning right = left: both references point to the same subtree and the other one is lost.
Swapping only the root or only nodes with two nonempty children; a one-child node must move its child to the other side too.
Swapping values instead of child references: the shape and null positions would remain wrong on asymmetric trees.
Visiting the same subtree twice through changed pointers while skipping the other. Recursing into both new children once, or both saved original children once, is correct.
Returning null after a successful swap, or forgetting to return the new root of a mirrored copy.
Claiming in-place recursion uses O(1) space; call frames require O(h). Distinguish that from the copy approach’s O(n) allocated output and clarify whether mutation is allowed in the interview.

Key Takeaway

A whole-tree mirror follows from one local left/right exchange at every node. Choose ownership deliberately: fresh mirrored copies preserve the caller’s tree, while in-place swaps reuse all nodes and applying them twice restores the original.