invert_binary_tree.py

from collections import deque
from typing import Optional


class TreeNode:
    """LeetCode provides this class; repeated here so the file runs standalone."""

    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None,
                 right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode #226 - Invert Binary Tree (Easy)
    https://leetcode.com/problems/invert-binary-tree/

    Mirror the tree: every node's left and right subtrees swap places.
    """

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """Recursive: swap the children, then recurse into both.

        Key insight: mirroring a tree is the same operation applied to every
        node - swap its two children. The recursion writes itself once you trust
        it: invert the left subtree, invert the right subtree, then swap them.

        Python's tuple assignment does the swap without a temporary variable,
        and both right-hand sides are evaluated before either is assigned - so
        the order of the two recursive calls is not a trap here.

        Time:  O(n) - every node is visited exactly once.
        Space: O(h) - recursion depth = tree height; O(n) if the tree is a chain.
        """
        if root is None:
            return None

        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

    def invert_tree_iterative(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """Iterative variant using an explicit queue (BFS).

        Worth having ready for the follow-up "what if the tree is deep enough to
        blow the recursion limit?" - the queue moves that state onto the heap.

        Time:  O(n)
        Space: O(n) - the queue holds up to a full level of the tree.
        """
        if root is None:
            return None

        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root