How do you invert a binary tree?

Q: How do you invert a binary tree?

**Target Audience:** Beginners preparing for coding interviews; you should know what a binary tree is. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the **Verified** section quotes the real output. ## 1. Why This Even Matters — A Story First Hold a printed organisation chart up to a mirror. Every manager is still above the same people, but everyone who was on the left is now on the right and the other way round, at every level of the chart. Inverting a binary tree is exactly that mirror image: at every node, the left and right children trade places. The question is famous for a reason outside computer science. In June 2015 Max Howell, the creator of the Homebrew package manager, [tweeted](https://x.com/mxcl/status/608682016205344768) that Google had turned him d

The problem

Question presented to candidate: "Given the root of a binary tree, invert it — mirror it so every node's left and right children are swapped — and return the root. Please write it in Python, then show me a version that would not hit the recursion limit."

What a strong answer should cover:

Inverting means swapping the left and right child at every node, not just the root; any traversal order works because each node is swapped once.
A recursive version (swap, then recurse, or recurse, then swap) and an iterative BFS with collections.deque.
O(n) time; O(h) space recursively, O(w) for BFS; in place, no new nodes.
The assignment-order bug: two separate assignments with recursive calls overwrite node.left before it is read.
Python specifics: the tuple swap node.left, node.right = invert(node.right), invert(node.left) evaluates the whole right-hand side first, so it is safe; the default recursion limit of 1000 makes BFS the safe choice for deep trees.

Clarifying questions expected:

"Should I invert in place or return a new tree?"
"How deep can the tree be?"

Code / implementation expected: Yes — a short recursive Python function, ideally with an iterative BFS version too.

dsa
binary-tree
recursion

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know what a binary tree is. Difficulty: Easy Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the Verified section quotes the real output.

1. Why This Even Matters — A Story First

Hold a printed organisation chart up to a mirror. Every manager is still above the same people, but everyone who was on the left is now on the right and the other way round, at every level of the chart. Inverting a binary tree is exactly that mirror image: at every node, the left and right children trade places.

The question is famous for a reason outside computer science. In June 2015 Max Howell, the creator of the Homebrew p

The solution is hidden so you can try first

12 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonRecursive invert on six trees, shown in level-order form

Practice

PythonIterative BFS invert, the two-step assignment bug, and a 100000-node chain