# The Mirror Flip

> Sometimes the fastest fix is to swap everything.

Canonical URL: <https://datadriven.io/problems/the_mirror_flip>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given the root of a binary tree (nested dict with 'val', 'left', 'right'), return a new tree where every node's left and right children are swapped recursively.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **recursive tree manipulation**. Inverting a binary tree is one of the simplest recursive problems, but it reveals whether candidates understand the base case, recursive case, and return value pattern for tree transformations.

---

### Break down the requirements

#### Step 1: Base case: null node

If the node is `None`, return `None`. There is nothing to invert.

#### Step 2: Swap left and right children

Exchange the node's `left` and `right` pointers.

#### Step 3: Recurse on both subtrees

After swapping, recursively invert the (now-swapped) left and right subtrees.

#### Step 4: Return the root

Return the current node so the parent can attach the inverted subtree.

---

### The solution

**Recursive swap at every node**

```python
def invert_tree(root):
    if root is None:
        return None
    temp = root.left
    root.left = root.right
    root.right = temp
    invert_tree(root.left)
    invert_tree(root.right)
    return root
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Each node is visited once.
> 
> **Space:** O(h) where h is the tree height, due to the recursion stack. O(log n) for balanced trees, O(n) for skewed trees.

> **Interviewers Watch For**
>
> Do you swap before or after recursing? Both work, but swapping first is more intuitive: 'fix this node, then fix the children.'

> **Common Pitfall**
>
> Swapping and then recursing on the original variable names. After `root.left = root.right`, the old left subtree is gone unless you saved it in a temp variable first.

---

## Common follow-up questions

- Can you do this iteratively using a queue? _(Tests BFS-based tree manipulation as an alternative to recursion.)_
- How would you verify the tree was correctly inverted? _(Tests writing a comparison function or using in-order traversal.)_
- What if the tree is extremely deep and recursion hits the stack limit? _(Tests iterative approaches or increasing Python's recursion limit.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_mirror_flip)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.