4.14.1 — Invert Binary Tree

LeetCode 226 · Easy · ★ Blind 75

The problem

Mirror the tree: every node's left and right children swap.

     4                4
   /   \            /   \
  2     7    →     7     2
 / \   / \        / \   / \
1   3 6   9      9   6 3   1

The pattern

A tree is defined recursively — a node plus two subtrees, each of which is a tree. So almost every tree algorithm is: do something at this node, then recurse into the children.

Here: swap this node's two children, then invert each subtree. That is the whole solution.

The most useful habit for tree problems is to trust the recursive call. Do not trace it. Assume invert(node.left) correctly inverts everything below, and only ask what this node has to do.

The solution

Python

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

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

        return root

TypeScript

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;

  [root.left, root.right] = [root.right, root.left];
  invertTree(root.left);
  invertTree(root.right);

  return root;
}

The if not root base case is not optional decoration. It is what makes the recursion end, and it also handles an empty tree and a node with only one child, because a missing child is just None.

The swap and the recursion can go in either order. Swap first then recurse, or recurse first then swap — both work, because swapping a node's children and inverting the subtrees are independent operations. Try both mentally; if you can see why order does not matter here, you understand what the recursion is doing.

The iterative version

Any recursive tree walk can be written with an explicit stack (or a queue, which makes it a breadth-first walk):

from collections import deque

def invertTree(self, root):
    if not root:
        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

Worth knowing for one reason: recursion uses the call stack, and on a degenerate tree — one that has become a straight line — that is O(n) frames deep and can overflow. An explicit structure has the same memory cost but on the heap, where there is far more room.

Complexity

O(n) time, since every node is visited once.

O(h) space for the recursion, where h is the height. That is O(\log n) for a balanced tree and O(n) for a degenerate one. Say "height", not "log n" — the log only holds if the tree is balanced, and nothing here promises that.

Where this goes next

Every problem in this chapter starts from the same question: what does this node do, and what does it need from its children?

• Symmetric Tree — is the tree its own mirror? Compare the left subtree against the right subtree, walking them in opposite directions.
• Maximum Depth, Same Tree, Diameter — all the same shape with different work at the node.

Next: 4.14.2 Maximum Depth of Binary Tree — the same recursion, returning a value up instead of mutating.