Invert Binary Tree (LeetCode 226): Understanding the Correct Recursive Approach

Invert Binary Tree (LeetCode 226)

Invert Binary Tree is one of the most popular beginner-friendly problems when starting with tree recursion. The task is simple: for every node in the binary tree, swap its left and right children.

However, many beginners struggle not with swapping — but with writing the correct base case. This post walks through an initial incorrect approach, explains why it fails, and then breaks down the correct recursive solution.

---

❌ First Attempt (Incorrect Base Case)

Here was my first approach when solving this problem:

class Solution:
    def invertTree(self, root):
        if not root.left or not root.right:
            return root

        self.invertTree(root.left)
        self.invertTree(root.right)

        root.left, root.right = root.right, root.left
        return root

Why this fails

The condition below causes the function to return too early:

if not root.left or not root.right:
    return root

This stops recursion whenever a node has only one child. But even nodes with a single child still need to be inverted.

For example:

    1
   /
  2

After inversion, it should become:

    1
     \
      2

Because the function returns early, the swap never happens — leading to an incorrect result.

---

✅ Correct Recursive Solution

The correct approach is to stop recursion only when the node itself is None. This ensures that every valid node gets processed.

class Solution:
    def invertTree(self, root):
        if not root:
            return None

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Why this works

• The base case handles only empty nodes
• Every valid node performs a swap
• Recursion continues safely down both subtrees

This mirrors the exact definition of inverting a binary tree.

---

🧠 Key Takeaway for Tree Problems

When working with binary trees, the base case is almost always:

if not root:
    return

Avoid stopping recursion based on child nodes. Let recursion reach the leaves naturally.

---

📌 Full Solution Code

You can find the complete implementation here:

👉 View the solution on GitHub

---

Conclusion: This problem is a great introduction to tree recursion. A small mistake in the base case can completely change the behavior of your solution — understanding this early will help you solve many tree problems with confidence.