Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Easy

Invert Binary Tree

Invert (mirror) a binary tree explained: swap the children at every node, recursive and BFS Python solutions, tested code, pitfalls and a live tree visual.

Also searched as: mirror a binary tree · flip a binary tree left to right

🌳

Try it live Free

Binary Search Tree & Traversals

Build a small BST in the lab and run in-order: then picture the mirrored tree, whose in-order output is exactly the reverse.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given the root of a binary tree, turn it into its mirror image: every node's left and right children swap places, all the way down. Return the root.

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

The key insight

Mirroring a tree means swapping the two children of every single node. It does not matter whether you swap first and recurse after, or recurse first and swap after; each node just has to be swapped exactly once. Any traversal that visits every node does the job.

Brute force first: Copying values into a list and rebuilding a mirrored tree is possible but needs extra space and care; swapping in place is shorter and O(1) extra per node.

Step-by-step approach

  1. If the node is None, return None.
  2. Swap node.left and node.right.
  3. Recursively invert the (new) left subtree and the (new) right subtree.
  4. Return the node so the caller can reattach it.

Python solution

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


def invert_tree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

Complexity

TimeO(n)
SpaceO(h)

Each node is swapped once. The recursion depth is the tree height h, which is the only extra space used.

Common mistakes

Frequently asked questions

What is the time and space complexity of inverting a binary tree?

O(n) time, since each node is touched once, and O(h) space for the recursion, where h is the height. A BFS version uses O(w) space for the queue instead.

What happens to the inorder traversal after inversion?

It is reversed. Inverting a binary search tree therefore produces a tree whose inorder traversal is in descending order.

Can I do it iteratively?

Yes. Put the root in a queue or stack, and for every node you pop, swap its children and push the non-null ones. Each node is still swapped exactly once.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.