Invert Binary Tree

Intuition

Inverting a tree is a naturally recursive task: the mirror of a tree is a node whose left child is the mirror of the original right subtree and whose right child is the mirror of the original left subtree. If we trust the recursion to correctly invert both subtrees, all that is left at each node is to swap the two returned references. The base case is an empty node, which is its own mirror. Because every node is visited exactly once and does a constant amount of work, the traversal is linear. This same structure can be rewritten iteratively with an explicit stack or queue if recursion depth is a concern.

Algorithm walkthrough

1. 1If the current node is null, return null (an empty tree mirrors to an empty tree).
2. 2Recursively invert the left subtree and capture the returned root.
3. 3Recursively invert the right subtree and capture the returned root.
4. 4Assign the inverted right subtree to node.left and the inverted left subtree to node.right.
5. 5Return the current node so the parent call can attach it.
6. 6The original root is returned once the top-level call unwinds.

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