Invert Binary Tree

Swap a node’s children, having first inverted each of those children’s own subtrees. The base case is a None node, which has nothing to invert.

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 | None) -> TreeNode | None:
        if root is None:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

Tracing root = [4,2,7,1,3,6,9] — Python evaluates the right side before assigning, so the entire right subtree (7, 6, 9) is fully inverted before the left subtree (2, 1, 3) even starts.

Watch the call stack: the right child is always entered first, and a node swaps only after both of its subtrees are done.

Complexity: every node is visited exactly once and does O(1) work (one swap) → O(n) time. The recursion depth equals the tree’s height → O(h) space, which is O(log n) for a balanced tree but can degrade to O(n) for a skewed one.

Recursion depth is bounded by tree height, which can blow the call stack on a very unbalanced tree (e.g. a 10,000-node “linked list” tree). A queue-based level-order walk avoids recursion entirely, trading stack depth for queue width.

from collections import deque

class Solution:
    def invertTree(self, root: TreeNode | None) -> TreeNode | None:
        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

Why prefer this: identical O(n) time — every node is still swapped once — but space is now bounded by the queue’s peak size (the tree’s maximum width) rather than its height. For a balanced tree that’s still O(n) in the worst case (the bottom level can hold ~n/2 nodes), so there’s no asymptotic win here — it’s a robustness tradeoff (no recursion limit) rather than a performance one.