Skip to main content
DSA patterns

Invert Binary Tree

easyTrees Must-doGoogleHomebrew (Classic)TCS

Problem statement

You're given the root of a binary tree. Invert it by swapping every node's left and right children, at every level and not just at the root, and return the root of the transformed tree. The result is a mirror image of the original: what was on the left is now on the right, all the way down, and whatever subtree came with it moves along too.

Examples

Example 1

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

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

Explanation: The tree is a balanced 7-node tree. Swapping every node's left and right children at every level mirrors it. Under 4, the nodes 2 and 7 trade places, and their own children trade places too (3 and 1 under 2, and 9 and 6 under 7).

Example 1

Example 2

Input: root = [2,1,3]

Output: [2,3,1]

Explanation: The root's two children, 1 and 3, simply trade places.

Example 2

Example 3

Input: root = []

Output: []

Explanation: There is nothing to swap in an empty tree, so it stays empty.

Hints

Hint 1: What does "invert" mean for a single node with no children? What about a node with just one child?

Approach

Optimal: Iterative swap, BFS

Intuition

Do the exact same swap as the recursive version, but drive it with a queue instead of function calls tracking what is left to visit. Process one node at a time: swap its children, then add whichever children exist to the queue so they get the same treatment later. This is a standard level-order (breadth-first) traversal with one extra step, the swap, at each node.

This version never grows a recursion stack, which matters for a tree so unbalanced (essentially a long chain) that recursion could hit a stack-depth limit.

Steps

  1. If the root is null, return null immediately.
  2. Put the root in a queue.
  3. While the queue is not empty, remove one node and swap its left and right pointers.
  4. After swapping, add whichever of the (now swapped) children are not null to the queue, so they get visited too.
  5. Once the queue is empty, every node has been swapped. Return the original root.

Dry run

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

queue before node popped after swap queue after
[4] 4 children become 7, 2 [7, 2]
[7, 2] 7 children become 9, 6 [2, 9, 6]
[2, 9, 6] 2 children become 3, 1 [9, 6, 3, 1]
[9, 6, 3, 1] 9, 6, 3, 1 each is a leaf, so no children to add []

The final level order is 4, 7, 2, 9, 6, 3, 1, which matches [4,7,2,9,6,3,1].

Edge cases: same as recursion. A null root returns immediately, and a leaf node's swap of two null children changes nothing.

Complexity

Time O(n) - The same as the recursive version: every node is taken off the queue once, and a swap plus pushing up to two children is a constant amount of work.

Space O(w) - The queue holds at most one level's worth of nodes at a time, where w is the tree's widest level. For a balanced tree that can be about n/2, so it is O(n) in the worst case, but the call stack is not used at all.

from collections import deque


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def invertTree(self, root: "Optional[TreeNode]") -> "Optional[TreeNode]":
        if root is None:
            return None

        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root


def build_tree(values):
    """Build a tree from a level-order list where None means a missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values):
            if values[i] is not None:
                node.left = TreeNode(values[i])
                queue.append(node.left)
            i += 1
        if i < len(values):
            if values[i] is not None:
                node.right = TreeNode(values[i])
                queue.append(node.right)
            i += 1
    return root


def serialize(root):
    """Level-order list as text, trailing nulls removed."""
    if root is None:
        return "[]"
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node:
            out.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            out.append("null")
    while out and out[-1] == "null":
        out.pop()
    return "[" + ",".join(out) + "]"


if __name__ == "__main__":
    for values in [[4, 2, 7, 1, 3, 6, 9], [2, 1, 3], []]:
        print(serialize(Solution().invertTree(build_tree(values))))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "mirror" or "invert" a binary tree, where every node's left and right children need to trade places
  • Idea: at every node, swap left and right, then apply the same rule to whatever is now in those two positions (recursively, or with a queue)
  • Cost: O(n) time either way; O(h) space recursively (tree height), O(w) space iteratively (widest level); a mirrored copy costs O(n) extra
  • Trap: forgetting the base case (null node) returns immediately, which is what stops both the recursion and the queue from running forever

Interview follow-ups

  • What if the tree could be enormous, too deep for a normal recursion stack?

    Switch to the iterative, queue-based version. It does the identical work (O(n) time) but tracks what is left to process in a queue on the heap instead of the call stack, so it is not limited by the stack-depth ceiling that a very tall, unbalanced tree could hit with recursion.

  • How would you check whether a tree is a mirror image of itself?

    That is the Symmetric Tree problem. Compare the left subtree with the right subtree using a helper that takes two nodes. Two nodes match if both are null, or both exist with equal values and a.left matches b.right and a.right matches b.left. You could also invert a copy of the tree and compare it with the original using Same Tree. That is why the copying approach from the brute force is useful here, since inverting in place would destroy the original. The helper is O(n) time and O(h) space and does not need the extra copy.

  • How would you adapt this for a tree stored across multiple machines, such as a replica set organized as a tree of nodes?

    You cannot swap pointers directly across machines. Each node would instead apply the swap to its own children locally and send the same "swap your children" message down to each of them. The hard part is no longer the algorithm. It is making sure every node applies the swap exactly once even if messages arrive out of order or get duplicated, which usually means attaching a version number or a unique operation ID to each swap request so a node can recognize and ignore one it has already applied.

Frequently asked questions

It does not, as long as you are consistent about which subtree the recursive calls act on. Whether you swap first and then recurse into the (already swapped) children, or recurse first and swap the two returned subtrees afterward, both reach the identical final tree. This is one of the rare problems where pre-order and post-order give the same answer, because the operation at each node (swap two pointers) does not depend on what happens above or below it.

You can, and it is correct with the same O(n) time. The cost is memory: a full second tree, plus the original if you keep it. In an interview, mention that the copy leaves the input untouched, which is useful if other code still reads the original, but the in-place swap is the normal answer because it needs no new nodes.

It is less about trees specifically and more a quick, unambiguous check that you can write correct recursive (or iterative, queue-driven) code under time pressure. The same base-case-plus-recursive-step thinking shows up in walking a directory tree, a dependency graph or an org chart of services. It became a famous interview example because it is small enough to finish in a few minutes but still shows whether someone understands recursion or has only memorized a template.

Only the sides change. The shape (how many nodes at each depth, which nodes are leaves) is preserved exactly, and it is just mirrored left to right. Two trees that are mirror images of each other always have the same height, the same total node count, and the same count of nodes at every depth.

The same idea generalizes. Instead of swapping two fixed pointers, reverse the order of the list of children at every node, then recurse (or use a queue) the same way. The core insight is that inverting is a purely local operation per node, so it can be applied node by node during any traversal, and it does not depend on there being exactly two children.

Overthinking it. Because the fix (node.left, node.right = node.right, node.left, applied everywhere) is so simple, people sometimes assume there must be a trick and reach for something more complicated. Another common slip is swapping only at the root, which mirrors the top two subtrees but leaves everything below them in the original order.