You’re in a coding interview. The interviewer says: “Invert a binary tree.” You know this is three lines of recursive code. But those three lines are a trap: the solution is so short that candidates rush through it, forget to return the root, skip the base case explanation, or answer follow-up questions on traversal order with “I think it doesn’t matter” instead of confidently explaining why.

This walkthrough covers both the recursive and iterative approaches, the tree traversal reasoning behind each, every edge case worth naming, and the follow-up questions interviewers reach for.

---

The Problem

Given the root of a binary tree, invert the tree (mirror it around its vertical center) and return the root. For every node, swap its left and right children. This applies recursively at every level. (LeetCode #226)

Example

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

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

The tree rooted at 4 has left child 2 (with children 1, 3) and right child 7 (with children 6, 9). After inversion, 4’s children become 7 (left) and 2 (right). Recursively, every parent-child relationship is mirrored. A None input returns None.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

The implementation is short enough that explanation quality carries significant weight. Interviewers are specifically watching how you reason about the recursive structure and how naturally you handle the base case.

Skill	What Interviewers Observe
Recursive decomposition	Do you frame it as “swap children, then recurse on both subtrees”?
Base case reasoning	Do you immediately identify None as the base case and explain why?
DFS vs. BFS awareness	Do you proactively offer the iterative BFS alternative?
Tree traversal fluency	Do you recognize this as pre-order DFS and explain why traversal order doesn’t matter?
Complexity on trees	Can you express O(n) time and O(h) space clearly?
Follow-up readiness	Can you extend to checking if two trees are mirrors?

---

Step 1: Clarifying Questions

1. Should I return the root, or modify in place and return nothing? Return the root. You’re modifying in place by reassigning child pointers, then returning the same root.

2. What should be returned for an empty tree? Return None. An empty tree is already its own mirror.

3. Is this a binary tree or a binary search tree? A plain binary tree. If it were a BST, inverting would destroy the BST property.

4. Does “invert” mean mirror horizontally (swap left/right)? Yes, swap left and right children at every node.

---

Step 2: A First (Non-Optimal) Idea

A candidate might think about collecting all nodes, rebuilding the tree in mirrored order, or performing a deep copy with swapped structure. These are O(n) but involve unnecessary allocation. The clean insight: you only need to swap child pointers in place. No new nodes needed.

Approach	Time	Space
Rebuild/copy (unnecessary)	O(n)	O(n)
Recursive swap	O(n)	O(h)
Iterative BFS/DFS swap	O(n)	O(n)

---

Step 3: The Key Insight

Inverting a tree is a self-similar operation: swap the current node’s children, then invert each subtree. The base case is None.

The traversal order (pre-order, post-order, in-order) doesn’t affect correctness. What matters is that every node eventually gets its children swapped. Pre-order (swap first, then recurse) is the most intuitive to reason about.

The iterative equivalent uses a queue (BFS) or stack (DFS): push the root, pop a node, swap its children, push both children for future processing.

---

Step 4: Optimal Strategy (Recursive)

1. If root is None, return None.
2. Swap: root.left, root.right = root.right, root.left.
3. Recurse on root.left and root.right.
4. Return root.

---

Python Implementation

Recursive — Clean and Concise (Recommended)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root: TreeNode) -> TreeNode:
    # Base case: empty tree is already inverted
    if root is None:
        return None

    # Swap left and right children at the current node
    root.left, root.right = root.right, root.left

    # Recursively invert both subtrees
    invertTree(root.left)
    invertTree(root.right)

    return root  # Return the same root — tree is modified in place

Iterative BFS — Stack-Safe for Deep Trees

from collections import deque

def invertTree(root: TreeNode) -> TreeNode:
    if root is None:
        return None

    queue = deque([root])

    while queue:
        node = queue.popleft()

        # Swap this node's children
        node.left, node.right = node.right, node.left

        # Enqueue children for processing (if they exist)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return root

Key implementation notes:

• Python’s tuple swap is atomic. root.left, root.right = root.right, root.left fully evaluates the right side before assignment. No temp variable needed.
• The recursive calls don’t need to capture the return value. The tree is modified in place.
• The iterative approach avoids Python’s recursion depth limit (~1000). For a balanced tree of 100 nodes the depth is ~7, but for pathologically skewed trees, recursion could overflow.
• For a balanced tree, recursive space O(log n) beats BFS space O(n). Recursive isn’t always worse on space.

---

Time & Space Complexity

Approach	Time	Space
Recursive	O(n)	O(h)
Iterative BFS/DFS	O(n)	O(n)

Time: Every node is visited exactly once. The swap is O(1). Total: O(n).

Space (recursive): Call stack depth equals tree height h. Balanced: O(log n). Skewed: O(n).

Space (iterative): Queue holds at most O(n) nodes. For a perfect binary tree, the last level alone contains n/2 nodes.

---

Common Interview Mistakes

1. Forgetting to return root. The tree is inverted in place, but the return contract is broken if you forget return root. The caller gets None.

2. Trying to invert without a base case. Without if root is None: return None, the function raises AttributeError on root.left.

3. Capturing recursive returns incorrectly. Writing root.left = invertTree(root.right) without first preserving root.left produces incorrect results. Always swap pointers first, then recurse.

4. Not mentioning the iterative alternative. Presenting only recursion without acknowledging BFS signals incomplete thinking.

5. Not explaining why traversal order doesn’t matter. Being able to say “correctness only requires every node gets its children swapped, regardless of visit order” demonstrates genuine understanding.

6. Treating this as too trivial to explain. The recursive solution is three lines. The explanation is the interview. Narrate the base case, the swap, and the recursion.

---

What a Strong Candidate Sounds Like

“Inverting a binary tree is a self-similar operation: swap the left and right children of the root, then invert each subtree. The base case is None: an empty tree is already its own mirror.

The recursive solution is three meaningful lines: check for None, swap the children, recurse on both. I’ll use Python’s tuple swap. Every node is visited once: O(n) time. Space is O(h) for the call stack, O(log n) for a balanced tree, O(n) worst case.

I can also do this iteratively with a BFS queue if recursion depth is a concern. Same O(n) time, O(n) space. I’ll go with recursive for clarity.”

---

Example Interview Dialogue

Interviewer: Invert a binary tree and return the root.

Candidate: Just to confirm: invert means mirror left and right children at every node, and I return the same root after modifying in place?

Interviewer: Correct.

Candidate: This is naturally recursive. Swap the root’s children, then recursively invert both subtrees. Base case: if the node is None, return None. Python’s tuple swap handles the pointer reassignment cleanly. O(n) time, O(h) space.

Interviewer: Does the order of the recursive calls matter?

Candidate: No. Correctness only requires that every node eventually gets its children swapped. Pre-order, post-order, any order works. I prefer swap-first because it’s easier to reason about: process the current node before descending.

Interviewer: How would you do this iteratively?

Candidate: Replace the call stack with a queue for BFS. Push the root, then in a loop: pop a node, swap its children, push both children if non-None. Same O(n) time, O(n) space. The advantage is avoiding recursion depth limits for very deep trees.

Interviewer: How would you check if two trees are mirrors?

Candidate: That’s LeetCode #101, Symmetric Tree. Write a helper isMirror(left, right) that returns True when both are None, False when only one is, and True when values match and isMirror(left.left, right.right) and isMirror(left.right, right.left) both hold. Same recursive structure, checking symmetry instead of performing a swap.

---

Related Problems

Invert Binary Tree is the entry point for a family of recursive tree problems:

• Symmetric Tree (LeetCode #101). Check if a tree is its own mirror. Same recursive decomposition, checking instead of swapping.
• Maximum Depth of Binary Tree (LeetCode #104). Classic recursive tree problem: 1 + max(depth(left), depth(right)).
• Balanced Binary Tree (LeetCode #110). Checks height balance at every node. Combines depth with a validity check.
• Subtree of Another Tree (LeetCode #572). Check if one tree appears as a subtree within another.

The jump from Invert Binary Tree to Symmetric Tree (#101) is the most common interview escalation.

---

Practice This in a Mock Interview

For an Easy problem, fluency and communication quality are everything. The goal isn’t to write three correct lines quickly. It’s to write three correct lines and explain exactly what each one does, handle every clarifying question confidently, and pivot cleanly to the iterative version or the Symmetric Tree follow-up when asked.

Start a mock interview for Invert Binary Tree on Intervu.

---

Related Problems to Practice

• Maximum Depth of Binary Tree — Simple recursive tree traversal.
• Balanced Binary Tree — Recursive height computation with early termination.
• Diameter of Binary Tree — Passing information up through recursive returns.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code