LeetCode 226: Invert Binary Tree Solution in Python – A Step-by-Step Guide

Imagine taking a binary tree and flipping it like a mirror, turning its left branches into right ones and vice versa—that’s the heart of LeetCode 226: Invert Binary Tree! This easy-level problem challenges you to swap the left and right children of every node, creating an inverted tree that reflects the original. Using Python, we’ll dive into two solutions: the Best Solution (a depth-first method) for its simplicity and elegance, and an Alternative Solution (a breadth-first method with a queue) for a different angle. With beginner-friendly explanations, detailed examples, and clear code breakdowns, this guide will help you master tree inversion and grow your coding skills. Let’s flip that tree!

What Is LeetCode 226: Invert Binary Tree?

In LeetCode 226: Invert Binary Tree, you’re given the root of a binary tree and tasked with inverting it by swapping each node’s left and right children. The result is a mirrored tree—a fun test of your ability to manipulate tree structures, distinct from challenges like LeetCode 225: Implement Stack using Queues.

Problem Statement

Input: Root node of a binary tree.
Output: Root node of the inverted tree.
Task: Swap the left and right children of every node.

Constraints

Number of nodes: 0 to 100.
Node values: -100 to 100.

Example

Original tree:

Inverted tree:

Every left-right pair is swapped to create the mirror image.

Understanding the Problem: How to Invert a Binary Tree

To solve LeetCode 226: Invert Binary Tree in Python, we need to transform the tree by swapping each node’s children. Unlike geometric puzzles like LeetCode 223: Rectangle Area, this is about restructuring a tree. We’ll explore two approaches: 1. Best Solution (Depth-First): O(n) time, O(h) space—simple and intuitive. 2. Alternative Solution (Breadth-First with Queue): O(n) time, O(w) space—processes level-by-level.

Let’s start with the best solution.

Best Solution: Depth-First Approach to Invert Binary Tree

Why This Is the Best Solution

The depth-first approach stands out as the best for LeetCode 226 because it naturally follows the tree’s structure, moving from root to leaves with clean, concise code. It’s efficient and easy to grasp, making it perfect for learners and problem-solvers alike.

How It Works

If the root is None, return None.
Swap the left and right children of the current node.
Continue processing the left and right subtrees in a depth-first way.

Step-by-Step Example

Example 1: Small Tree Inversion

Tree:

   2
  / \
 1   3

Start at root (2).
Swap 1 and 3: Left = 3, Right = 1.
Subtrees (3 and 1) are leaves—no further swaps needed.

Result:

   2
  / \
 3   1

Example 2: Larger Tree

Tree:

Root (4): Swap 2 and 7 → Left = 7, Right = 2.
Node 7: Swap 6 and 9 → Left = 9, Right = 6.
Node 2: Swap 1 and 3 → Left = 3, Right = 1.

Result matches the example above.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # Line 1: Check for empty tree
        if not root:
            return None  # Nothing to invert

        # Line 2: Swap left and right children
        root.left, root.right = root.right, root.left  # O(1) swap
        # e.g., root=4 swaps left=2 with right=7

        # Line 3: Process left subtree
        self.invertTree(root.left)  # e.g., handle node 7
        # Line 4: Process right subtree
        self.invertTree(root.right)  # e.g., handle node 2

        # Line 5: Return the root of the inverted tree
        return root  # Tree is now mirrored

Time Complexity: O(n) – visits each node once.
Space Complexity: O(h) – stack depth depends on tree height.

Alternative Solution: Breadth-First Approach with Queue

Why an Alternative Approach?

The breadth-first approach uses a queue to process the tree level-by-level, offering a different way to invert it. It’s a solid choice if you enjoy queue-based methods or want to see the tree transform in a layered fashion.

How It Works

Start with a queue containing the root.
For each node, swap its children and add non-null children to the queue.
Keep going until the queue is empty.

Step-by-Step Example

Tree:

    4
   / \
  2   7

Queue starts with [4].
Process 4: Swap 2 and 7, add 7 and 2 to queue → Queue = [7, 2].
Process 7: No children.
Process 2: No children.

Result:

    4
   / \
  7   2

Code for Breadth-First Approach

from collections import deque

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

        # Start queue with root
        queue = deque([root])

        # Process nodes level-by-level
        while queue:
            node = queue.popleft()  # Get next node (O(1))
            # Swap its children
            node.left, node.right = node.right, node.left
            # Add children to queue if they exist
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root

Time Complexity: O(n) – processes each node once.
Space Complexity: O(w) – queue size depends on tree width.

Comparing the Two Solutions

Best Solution (Depth-First):

Pros: Clean, follows tree structure, minimal code.
Cons: Stack space tied to height.

Alternative Solution (Breadth-First with Queue):

Pros: Queue-based, level-wise processing.
Cons: More code, space tied to width.

The depth-first method is our best for its simplicity and natural fit with trees.

Additional Examples and Edge Cases

Empty Tree

Input: None.
Output: None.
Both solutions handle this with an initial check.

Single Node

Input: [1].
Output: [1].
Swap has no effect (children are None).

Skewed Tree

Becomes:

Both approaches work flawlessly.

Complexity Breakdown

Depth-First:

Time: O(n).
Space: O(h) – up to n in skewed trees.

Breadth-First with Queue:

Time: O(n).
Space: O(w) – up to n/2 in complete trees.

Both are time-efficient; space depends on tree shape.

Key Takeaways for Beginners

Tree Inversion: Swapping children creates a mirror.
Depth-First: Moves from root to leaves.
Breadth-First: Handles levels with a queue.
Python Tip: deque ensures fast queue operations—check out [Python Basics](/python/basics).

Final Thoughts: Master Tree Inversion Now

LeetCode 226: Invert Binary Tree in Python is a fantastic way to tackle tree manipulation. The depth-first solution shines with its simplicity, while the breadth-first approach with a queue offers a layered twist. Want more tree challenges? Explore LeetCode 104: Maximum Depth of Binary Tree or LeetCode 100: Same Tree. Ready to flip some trees? Head to Solve LeetCode 226 on LeetCode and mirror that tree today!