LeetCode 226: Invert Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to invert the tree and return its root. Inverting means every node swaps its left child and right child.

For example, LeetCode gives this input and output: root = [4,2,7,1,3,6,9] becomes [4,7,2,9,6,3,1]. The constraints say the tree has between 0 and 100 nodes, and each node value is between -100 and 100.

Input and Output

LeetCode gives the usual binary tree node shape:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The required function shape is:

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        ...

Examples

Example 1:

Input:  root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

The original tree is:

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

After inversion:

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

Every node swapped its left and right children.

Example 2:

Input:  root = [2,1,3]
Output: [2,3,1]

Original:

    2
   / \
  1   3

Inverted:

    2
   / \
  3   1

Example 3:

Input:  root = []
Output: []

An empty tree stays empty.

First Thought: Traverse Every Node

To invert the whole tree, every node must be visited once.

At each node, we only need one local operation:

swap node.left and node.right

The question becomes: how do we visit every node?

A binary tree naturally supports recursive traversal. Each subtree is itself a smaller binary tree.

So the same operation works for:

1. The root.
2. The left subtree.
3. The right subtree.

Key Insight

To invert a tree rooted at root, we can do this:

1. Invert the left subtree.
2. Invert the right subtree.
3. Swap the two inverted subtrees.

The base case is an empty tree.

If root is None, there is nothing to invert, so we return None.

This gives a very small recursive solution.

Algorithm

For a node root:

1. If root is None, return None.
2. Recursively invert root.left.
3. Recursively invert root.right.
4. Swap root.left and root.right.
5. Return root.

In Python, the swap can be written directly:

root.left, root.right = root.right, root.left

Then we continue recursively into the children.

There are two equivalent orders:

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

or:

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

Both are correct. The second version makes the recursive structure more explicit, so we will use it.

Correctness

We prove the algorithm is correct by induction on the size of the tree.

For an empty tree, the algorithm returns None. This is correct because the inverse of an empty tree is still empty.

Now consider a non-empty tree with root root.

Assume the algorithm correctly inverts the left subtree and the right subtree. This is the induction hypothesis.

The algorithm first computes:

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

By the induction hypothesis, left is the inverted original left subtree, and right is the inverted original right subtree.

Then the algorithm assigns:

root.left = right
root.right = left

This places the inverted original right subtree on the left side, and the inverted original left subtree on the right side.

That is exactly the definition of a mirrored binary tree.

Therefore, the tree rooted at root is correctly inverted. By induction, the algorithm correctly inverts the whole tree.

Complexity

Here, n is the number of nodes, and h is the height of the tree.

For a balanced tree, h = O(log n).

For a skewed tree, h = O(n).

Implementation

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

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

        root.left = right
        root.right = left

        return root

Code Explanation

The base case handles an empty subtree:

if root is None:
    return None

This also handles the case where the whole input tree is empty.

Then we recursively invert both children:

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

After these calls finish, left and right already point to inverted subtrees.

Now we swap them:

root.left = right
root.right = left

Finally, we return the current root:

return root

The root node itself does not change. Only its child pointers change.

Testing

To test tree problems, it helps to convert between list representation and tree representation.

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    root = TreeNode(values[0])
    q = deque([root])
    i = 1

    while q and i < len(values):
        node = q.popleft()

        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1

        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1

    return root

def tree_to_list(root):
    if root is None:
        return []

    result = []
    q = deque([root])

    while q:
        node = q.popleft()

        if node is None:
            result.append(None)
            continue

        result.append(node.val)
        q.append(node.left)
        q.append(node.right)

    while result and result[-1] is None:
        result.pop()

    return result

Now we can test the solution:

def run_tests():
    s = Solution()

    root = build_tree([4, 2, 7, 1, 3, 6, 9])
    assert tree_to_list(s.invertTree(root)) == [4, 7, 2, 9, 6, 3, 1]

    root = build_tree([2, 1, 3])
    assert tree_to_list(s.invertTree(root)) == [2, 3, 1]

    root = build_tree([])
    assert tree_to_list(s.invertTree(root)) == []

    root = build_tree([1])
    assert tree_to_list(s.invertTree(root)) == [1]

    root = build_tree([1, 2, None, 3])
    assert tree_to_list(s.invertTree(root)) == [1, None, 2, None, 3]

    print("all tests passed")

run_tests()