Trees Pattern

Invert Binary Tree

Given the root of a binary tree, produce its mirror image — at every node, the left subtree and the right subtree trade places — and return the root. The values stay where they are relative to their node; only the links move. The tree is modified in place and the same root node is returned. An empty tree (null root) is returned unchanged.

CONSTRAINTS

The number of nodes in the tree is in the range [0, 100]
-100 <= Node.val <= 100
Modify the existing nodes in place; do not build a second tree
Return the root of the modified tree

EXAMPLE 1

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

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

The mirror rule applies at every node, not just the root: 4's children flip to 7 and 2, and then 7's own children 6 and 9 flip to 9 and 6 as well. Flipping only the top level would be wrong.

EXAMPLE 2

Input: root = [2,1,3]

Output: [2,3,1]

One flip at the root is enough here, because 1 and 3 are leaves with nothing beneath them to flip.

EXAMPLE 3

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

Output: [1,null,2,null,3]

A missing child mirrors too. 1's left subtree moves to the right and its (empty) right side moves to the left, so what was a left-leaning chain becomes a right-leaning one.

EXAMPLE 4

Input: root = []

Output: []

An empty tree is its own mirror. There is nothing to swap, and returning null is the correct answer rather than an error.

Should I modify the tree in place or return a new tree?

In place — swap the existing links and hand back the same root. Building a copy would double the memory for no benefit, though it is worth confirming, since a caller who still needs the original would want the copy.

Do the node values change, or only the links?

Only the links. A node keeps its value and simply ends up in the mirrored position, which is why duplicate values cause no trouble.

What if a node has just one child?

It still swaps. The empty side moves over and the child moves to the other side; treating a missing child as 'nothing to do' is a common mistake.

Is any traversal order required?

No, and that is unusual — the answer comes out the same whether you swap before or after recursing. Most tree problems are not that forgiving, so it is worth asking why this one is.

Mirroring a tree means: hold it up to a mirror and rebuild what you see. A node that sat on the left of its parent now sits on the right, and this has to be true at every level, not just under the root — in the reflection, a deep node's descendants are mirrored too. So the operation is not "swap the root's two children"; it is "swap every node's two children."

That last sentence, read literally, is already the algorithm. But it is worth seeing why one line of swapping is enough, because the same reasoning is what makes almost every tree recursion work.

Cutting the problem into two smaller copies of itself

Look at the root. In the mirrored tree, the entire left subtree has to end up hanging off the right link, and the entire right subtree off the left link. That is a single pointer swap. But the two subtrees also have to be mirrored internally, and here is the point: "mirror this subtree" is the identical problem we started with, only on a smaller tree.

So the job splits cleanly into three pieces:

- Swap this node's two links.

- Mirror whatever now hangs on the left.

- Mirror whatever now hangs on the right.

And the smallest possible case answers itself: an empty tree, null, is already its own mirror, so there is nothing to do and we return. Every recursive call moves strictly one level down toward that case, so the process terminates. Correctness then rides up from the bottom: leaves are trivially mirrored, a node whose two subtrees are correctly mirrored and whose links are swapped is itself correctly mirrored, and so on up to the root.

python

def invert(node):
    if node is None:            # empty tree is already its own mirror
        return None
    node.left, node.right = node.right, node.left   # the one real action
    invert(node.left)           # mirror the subtrees, whichever side they now sit on
    invert(node.right)
    return node

You are not tracing what happens inside those two calls. You assume each one correctly mirrors the subtree it is handed — which is legitimate for exactly the reason above — and you write only the one honest step that belongs to this node.

Does the order matter here?

The traversal question from the previous problem was: when does a node do its work — before its children, or after? Here, unusually, the answer is "either." Swap first and then recurse, and the calls simply receive the subtrees at their new addresses; the left call now handles what used to be the right subtree, mirrors it correctly, and the fact that it is sitting on the other side is irrelevant to it. Recurse first and then swap, and each subtree gets mirrored internally before being moved wholesale; moving an already-correct subtree does not disturb anything inside it.

The reason both work is that the swap at a node and the mirroring inside its subtrees touch disjoint links. The swap rewrites this node's two link fields; the recursive work rewrites link fields strictly deeper down. Two operations that never write the same memory can happen in either order. Hold on to that test — it is the general reason a tree problem is order-free, and it is exactly what fails in problems like Flatten Binary Tree, where the node's own rewiring destroys the very pointer the recursion still needs to find its subtree. There, order is forced.

Crucial Noteswap the two links as one atomic step. In a language without tuple assignment you need a temporary — tmp = node.left; node.left = node.right; node.right = tmp. Writing node.left = node.right first overwrites the only reference to the old left subtree, and that subtree is then unreachable: half the tree quietly disappears and both sides end up as copies of the original right subtree.

Worked example:root 4 with children 2 and 7; 2 has 1 and 3; 7 has 6 and 9
- At 4: swap, so 7 is now on the left and 2 on the right. Recurse into the left link, which now holds 7.
- At 7: swap, so 9 is on the left and 6 on the right. Both are leaves; each call swaps two nulls, which is harmless, and returns.
- Back at 4, recurse into the right link, which holds 2. Swap gives 3 on the left, 1 on the right; both leaves, done.
- Reading the finished tree level by level: 4, then 7 and 2, then 9, 6, 3, 1 — the original list read right-to-left within each level, exactly as a mirror would show it.

Cost, and the reflex to keep

Each node is visited once and does a constant amount of work — one null check, one swap — so the time is O(N). There is no extra data structure, but the recursion holds one frame per node on the current root-to-node path, so the space is O(H) where H is the height: about log₂N for a balanced tree, and N in the worst case of a single chain. Swapping level by level with a queue (the breadth-first walk introduced in Level Order Traversal) is an equally valid alternative with the same O(N) time and O(width) memory — useful to mention when an interviewer raises deep-recursion concerns.

The habit worth taking away: when a transformation is described as applying "at every node," stop hunting for a loop over levels and instead ask what the single node's job is and whether the rest is the same problem on the two subtrees. Here it was one swap plus two smaller mirrors. That decomposition — one local action, two recursive calls, one base case — is the skeleton behind Same Tree, Symmetric Tree (which is this mirror idea used as a comparison rather than a modification), and Maximum Depth. The only thing that changes across those problems is what the local action is, and whether it must happen before or after the calls.

Interactive Strategy Visualization