Invert Binary Tree | Leetcode 226

Welcome to our deep dive on Invert Binary Tree (Leetcode 226). This problem is famously meme'd in the CS community ("Max Howell couldn't invert a binary tree on a whiteboard..."). It remains one of the cleanest structural introductions to Tree Traversal and Recursive DFS logic possible.

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Inverting a Binary Tree formally means that for every single node in the tree, you seamlessly swap its left and right children explicitly.

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

Approach: Recursive DFS (Depth-First Search) O(N)

Recursion thrives on breaking down trees functionally. The core premise is brilliantly simple:

1. Base Case: If the root is null, return null. There's nothing to recursively invert!
2. Swap Phase: Grab the left child and right child, and swap them completely.
3. Recursive Leap: Call invertTree on the new left branch and the new right branch.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
            
        # Swap children
        root.left, root.right = root.right, root.left
        
        # Invert recursively
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (226)