LeetCode 226: Invert Binary Tree — Step-by-Step Visual Trace

#leetcode #algorithms #python #datastructures

Easy — Binary Tree | Recursion | Depth-First Search | Tree Traversal

The Problem

Given the root of a binary tree, invert the tree by swapping the left and right children of every node, and return the root of the inverted tree.

Approach

Use a recursive depth-first approach to traverse the tree. At each node, swap the left and right children, then recursively invert both subtrees. The base case returns None for null nodes.

Time: O(n) · Space: O(h)

Code

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

        # Swap left and right subtrees
        root.left, root.right = root.right, root.left

        # Recursively invert left and right subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root