Invert a Binary Tree

Table of Contents +

This one looks scary because of the name. But it is one of the friendliest tree questions you will get. The interviewer is not testing some fancy trick here. They want to see if you are comfortable walking through a tree with recursion. So if you can swap two things and then call yourself again, you already have the answer.

🌳 The Problem

You are given the root of a binary tree. A binary tree is a structure where each node holds a value and points to at most two children, a left child and a right child. Your job is to invert it. To invert means to mirror the whole tree. So every node’s left child and right child trade places.

Picture holding the tree up to a mirror. Whatever was on the left now shows up on the right.

Before:                 After:

        4                       4
      /   \                   /   \
     2     7                 7     2
    / \   / \               / \   / \
   1   3 6   9             9   6 3   1

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

See how at every node the two children just flipped sides? That is the whole task.

🤔 How do we think about it?

A first instinct is to do this level by level. You could use a queue, visit each node, and swap its two children one at a time. That works fine and it is a real solution. But carrying a queue around feels like extra setup for something this small. You have to set it up, push nodes, pop nodes, and check when it is empty.

Now think about what swapping really means. At any node you only do one thing. You swap its left and right children. Then the same exact job needs to happen on each child. That is the same problem on a smaller tree. When a big problem is just a smaller copy of itself, recursion fits perfectly. Recursion is when a function solves a small piece and then calls itself to handle the rest.

So the clean idea is short. Swap the two children at the current node. Then ask the function to invert the left subtree and the right subtree. When a node is empty, there is nothing to do, so you just stop.

📝 Steps to invert the tree

If the current node is empty (null), return. This is your stopping point.
Swap the left child and the right child of the current node.
Call the same invert function on the left child.
Call the same invert function on the right child.
Return the root once everything is swapped.

💻 The Code

We build the sample tree, print it left to right (an in-order traversal), invert it, then print it again so you can see the mirror happen.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

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

# Swap the children, then recurse on both sides
def invert(root):
    if root is None:                 # empty node, nothing to do
        return None
    root.left, root.right = root.right, root.left  # swap children
    invert(root.left)                # fix the left subtree
    invert(root.right)               # fix the right subtree
    return root

# Print values left to right (in-order)
def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.val, end=" ")
    inorder(root.right)

root = Node(4)
root.left = Node(2)
root.right = Node(7)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(9)

print("Before:", end=" ")
inorder(root)
print()

invert(root)

print("After: ", end=" ")
inorder(root)
print()

The output of the above code will be:

Before: 1 2 3 4 6 7 9
After:  9 7 6 4 3 2 1

Notice the trick we used to check the answer. An in-order traversal of the tree before inverting gives the values in one order. After inverting, the same traversal gives that exact list reversed. So if your “After” line is the mirror of your “Before” line, you know the swap worked.

⏱️ Time and Space Complexity

We touch every node once and do a tiny bit of constant work at each. So the time is the same for both approaches. The space is what tells them apart. Here n is the number of nodes and h is the height of the tree.

Approach	Time	Space
Recursion (swap then recurse)	O(n)	O(h)
Iterative with a queue	O(n)	O(n)

The recursion uses O(h) space because of the call stack. The stack only holds the nodes on the path from the root down to where you currently are. And that path is at most the height of the tree.

Tip

In an interview, say out loud that the recursion needs O(h) stack space, where h is the tree height. For a balanced tree that is about log n. For a tree that leans to one side like a long chain, the height can be n. Mentioning this shows you understand the hidden cost of recursion.

🧩 Key Takeaways

✅ Inverting a tree means swapping the left and right child at every single node.
✅ The clean solution is recursion. Swap the two children, then invert both subtrees.
✅ Your stopping point is an empty node. When the node is null, just return.
✅ Time is O(n) since you visit each node once. Space is O(h) for the recursion stack.
✅ A quick self-check: an in-order traversal after inverting is the reverse of the in-order traversal before.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Maximum Depth of a Binary Tree
Tree Traversals

Previous Maximum Depth of a Binary Tree Next Lowest Common Ancestor

Share & Connect

Share on LinkedIn