Convert a binary tree to its mirror image

You are at a Bloomberg interview when the interviewer draws a binary tree on the whiteboard and asks: "Can you write a function to invert this tree?" This is a problem that famously went viral in the developer community, and it remains one of the most-asked binary tree questions. Known as Invert Binary Tree on other platforms, it tests your ability to think recursively and manipulate tree structures in-place.

TL;DR

At every node, swap its left and right children, then recurse into both subtrees. The base case returns when the node is null. This mirrors the entire tree in O(n) time, visiting each node once to perform a constant-time swap. Space is O(n) worst case due to the call stack on a skewed tree, or O(log n) for a balanced tree.

The Problem

Given the root TreeNode of a binary tree, write a method to convert the tree to its mirror image and return its root node.

Input tree (t1):        Mirror (t2):
     1                      1
    / \                    / \
   2   3        ->        3   2
      / \                / \
     4   5              5   4

The mirror image flips every subtree so that what was on the left is now on the right and vice versa. Node 2, originally the left child of 1, becomes the right child. Node 3 and its subtree move to the left, and within that subtree, nodes 4 and 5 also swap positions.

Visualizing the Mirror

Here is the original tree from the problem example:

And here is its mirror image after the transformation:

Notice that the root stays in place. Every parent-child relationship is reflected: left children become right children and right children become left children, all the way down.

Building Intuition

Think of holding the tree up to a mirror. The reflection swaps left and right at every level. To produce this result programmatically, you need to swap the left and right children of every single node in the tree.

The recursive insight is that mirroring the whole tree is the same as:

1. Swap the current node's left and right children
2. Mirror the left subtree (which was originally the right subtree)
3. Mirror the right subtree (which was originally the left subtree)

This is a pre-order traversal where the "work" at each node is a simple swap.

A Larger Example

To see the pattern more clearly, consider a full binary tree with 7 nodes:

After mirroring, every level is reversed:

Node 3 (with children 7, 6) is now on the left, and node 2 (with children 5, 4) is on the right. Within each subtree, the children have also swapped.

Tracing the Recursion

Here is how the recursive calls flow for the original example tree:

At node 1, we swap its children (left becomes 3, right becomes 2). Then we recurse into node 3 and swap its children (left becomes 5, right becomes 4). Node 2 is a leaf with no children to swap. Every node gets visited once, and the tree is fully mirrored.

Edge Cases

Null tree: If the root is null, return null immediately. There is nothing to mirror.

Single node: A tree with one node is its own mirror. The function swaps null with null (a no-op) and returns the root.

Skewed tree: A tree where every node has only a left (or only a right) child becomes a tree where every node has only the opposite child. The recursion depth equals the number of nodes.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public TreeNode mirrorTree(TreeNode root) {
    if (root == null) return null;
    swapChildren(root);
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
  }

  private void swapChildren(TreeNode node) {
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
  }
}

The swapChildren helper performs a standard three-variable swap. The main method checks for null (the base case), swaps the current node's children, then recurses into both subtrees. Finally, it returns the root so the caller has a reference to the modified tree.

The swap happens before the recursive calls (pre-order). This means by the time we recurse into root.left, that pointer already refers to what was originally root.right. The order does not affect correctness because every node gets swapped exactly once regardless of traversal order.

Complexity Analysis

Time: O(n)

Every node is visited exactly once. At each node, the swap is O(1). Total work: O(n) where n is the number of nodes.

Space: O(n)

The space comes entirely from the recursive call stack. For a balanced tree, the maximum recursion depth is O(log n). For a completely skewed tree where every node has only one child, the depth is O(n). No additional data structures are allocated since the tree is modified in-place.

Iterative Alternative

You can also solve this problem iteratively using a queue (BFS) or stack (DFS). Push the root, and at each step pop a node, swap its children, and push both non-null children. This avoids recursion but uses O(w) space where w is the maximum width of the tree. For a balanced tree, w can be up to n/2 at the last level, so the iterative approach does not necessarily save space.

The recursive approach is preferred in interviews because it is concise, easy to explain, and directly maps to the tree's recursive structure.

Common Mistakes

1. Forgetting the base case. Without the null check, the function will throw a NullPointerException when it reaches a leaf node's child.

2. Swapping values instead of subtrees. Some candidates swap node.left.val and node.right.val instead of swapping the child pointers. This only works for the immediate children and fails to mirror the subtrees below them.

3. Returning a new tree. The problem asks you to modify the tree in-place and return its root. Creating new nodes is unnecessary and wastes memory.

4. Double-swapping. If you swap children and then accidentally recurse using the old variable names without accounting for the swap, you may process the same subtree twice. Using the helper method avoids this confusion.

Interview Tips

• Start with the recursive structure. Tell the interviewer: "Mirroring a tree means swapping children at every node. Since a tree is recursive, I will use recursion."
• Draw the before and after. Sketch a small tree (3-5 nodes) and show the mirror. This demonstrates understanding before writing code.
• Mention the traversal order. Explain that pre-order, in-order, and post-order all work. Pre-order is the most natural because you swap first, then recurse.
• Discuss the iterative alternative. If asked, describe the BFS approach with a queue. This shows breadth of knowledge.
• Highlight the O(n) time and O(n) space. Be specific about the worst-case space coming from the call stack on a skewed tree.

Key Takeaways

• Mirroring a binary tree swaps the left and right children of every node. The recursive solution is three lines of logic: null check, swap, recurse on both subtrees.
• Time complexity is O(n) because each node is visited once with O(1) work. Space is O(n) worst case from the recursion stack.
• The traversal order (pre-order, in-order, post-order) does not matter for correctness. Pre-order is the most intuitive.
• This problem is a building block for related tree problems like checking symmetry, comparing two trees, and serialization/deserialization.
• Always draw a small example and trace through the recursion before coding. A 3-node tree is enough to verify your approach handles the swap correctly.

Practice and Next Steps

Once you are comfortable mirroring a tree, try these related problems to deepen your understanding:

• Check if a binary tree is symmetric (compare left and right subtrees as mirror images)
• Find the height of a binary tree (same recursive traversal pattern)
• Check if two binary trees are structurally identical

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies.

Solutions in Other Languages

Python

class Solution:
    def mirror_tree(self, root):
        if root is None:
            return None
        self.swap_children(root)
        self.mirror_tree(root.left)
        self.mirror_tree(root.right)
        return root

    def swap_children(self, node):
        temp = node.left
        node.left = node.right
        node.right = temp

JavaScript

class Solution {
  mirrorTree(root) {
    if (root === null) return null;
    this.swapChildren(root);
    this.mirrorTree(root.left);
    this.mirrorTree(root.right);
    return root;
  }

  swapChildren(node) {
    const temp = node.left;
    node.left = node.right;
    node.right = temp;
  }
}

TypeScript

class Solution {
  mirrorTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return null;
    this.swapChildren(root);
    this.mirrorTree(root.left);
    this.mirrorTree(root.right);
    return root;
  }

  swapChildren(node: TreeNode): void {
    const temp = node.left;
    node.left = node.right;
    node.right = temp;
  }
}

C++

class Solution {
public:
  TreeNode *mirrorTree(TreeNode *root) {
    if (root == nullptr)
      return nullptr;
    swapChildren(root);
    mirrorTree(root->left);
    mirrorTree(root->right);
    return root;
  }

private:
  void swapChildren(TreeNode *node) {
    TreeNode *temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
};

Go

func (s *Solution) MirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    swapChildren(root)
    s.MirrorTree(root.Left)
    s.MirrorTree(root.Right)
    return root
}

func swapChildren(node *TreeNode) {
    temp := node.Left
    node.Left = node.Right
    node.Right = temp
}

Scala

class Solution {
  def mirrorTree(root: TreeNode): TreeNode = {
    if (root == null) return null
    swapChildren(root)
    mirrorTree(root.left)
    mirrorTree(root.right)
    root
  }

  private def swapChildren(node: TreeNode): Unit = {
    val temp = node.left
    node.left = node.right
    node.right = temp
  }
}

Kotlin

class Solution {
  fun mirrorTree(root: TreeNode?): TreeNode? {
    if (root == null) return null
    swapChildren(root)
    mirrorTree(root.left)
    mirrorTree(root.right)
    return root
  }

  private fun swapChildren(node: TreeNode) {
    val temp = node.left
    node.left = node.right
    node.right = temp
  }
}

Swift

class Solution {
    @discardableResult
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil { return nil }
        swapChildren(root!)
        mirrorTree(root!.left)
        mirrorTree(root!.right)
        return root
    }

    private func swapChildren(_ node: TreeNode) {
        let temp = node.left
        node.left = node.right
        node.right = temp
    }
}

Rust

impl Solution {
    pub fn mirror_tree(&self, mut root: Option<Box<TreeNode>>) -> Option<Box<TreeNode>> {
        if root.is_none() {
            return None;
        }
        let node = root.as_mut().unwrap();
        Self::swap_children(node);
        node.left = self.mirror_tree(node.left.take());
        node.right = self.mirror_tree(node.right.take());
        root
    }

    fn swap_children(node: &mut Box<TreeNode>) {
        std::mem::swap(&mut node.left, &mut node.right);
    }
}

C#

public class Solution {
    public TreeNode? MirrorTree(TreeNode? root) {
        if (root == null) return null;
        SwapChildren(root);
        MirrorTree(root.left);
        MirrorTree(root.right);
        return root;
    }

    private void SwapChildren(TreeNode node) {
        var temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

Dart

class Solution {
  TreeNode? mirrorTree(TreeNode? root) {
    if (root == null) return null;
    swapChildren(root);
    mirrorTree(root.left);
    mirrorTree(root.right);
    return root;
  }

  void swapChildren(TreeNode node) {
    TreeNode? temp = node.left;
    node.left = node.right;
    node.right = temp;
  }
}

PHP

class Solution {
    public function mirrorTree(?TreeNode $root): ?TreeNode {
        if ($root === null) return null;
        $this->swapChildren($root);
        $this->mirrorTree($root->left);
        $this->mirrorTree($root->right);
        return $root;
    }

    private function swapChildren(TreeNode $node): void {
        $temp = $node->left;
        $node->left = $node->right;
        $node->right = $temp;
    }
}

Ruby

class Solution
  def mirror_tree(root)
    return nil if root.nil?
    swap_children(root)
    mirror_tree(root.left)
    mirror_tree(root.right)
    root
  end

  def swap_children(node)
    temp = node.left
    node.left = node.right
    node.right = temp
  end
end