Invert Binary Tree

Inverting a tree just means swapping the left and right child at every node. There isn’t really a slow-vs-fast tradeoff here — both approaches below are O(n), they just differ in how they walk the tree.

Recursive (DFS)

Time O(n)Space O(h)

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:

1 / 5

comparingresult

Recurse to the leaves of the right subtree first: 9 and 6. A leaf has no children to swap.

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.

Iterative (BFS)

Time O(n)Space O(n)

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.