Invert Binary Tree#

Problem#

Given the root of a binary tree, invert it (mirror it left to right) and return the root. Inverting means swapping the left and right child of every node in the tree.

Example#

The tree with root 4, children 2 and 7, and grandchildren 1, 3, 6, 9 becomes root 4 with children 7 and 2 and grandchildren 9, 6, 3, 1. An empty tree returns an empty tree.

Optimal approach#

This is a direct recursion. At each node, swap its two children, then recurse into both subtrees so they get inverted as well. The base case is a null node, which you return unchanged. Because you visit every node exactly once and do constant work per node, the traversal is linear. An iterative version with a stack or queue works identically; the recursive form is the shortest to write.

Solution#

 1class TreeNode:
 2    def __init__(self, val=0, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7
 8def invert_tree(root: TreeNode | None) -> TreeNode | None:
 9    if root is None:
10        return None
11    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
12    return root
13
14
15root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)),
16                   TreeNode(7, TreeNode(6), TreeNode(9)))
17inverted = invert_tree(root)
18print(inverted.left.val, inverted.right.val)              # 7 2
19print(inverted.left.left.val, inverted.left.right.val)    # 9 6

Complexity#

• Time: O(n), one visit per node.
• Space: O(h), the recursion stack, where h is the tree height.

See the trees topic for more traversal problems, then continue the 60-day challenge.