Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Intuition

To invert a binary tree, we need to swap the left and right children of every node in the tree. We can do this recursively. For each node, we first swap its left and right children, and then recursively call the function on both the left and right subtrees.

Complexity

• Time Complexity: $O(N)$ where $N$ is the number of nodes in the tree, since we visit each node exactly once.
• Space Complexity: $O(H)$ where $H$ is the height of the tree. This is the space used by the call stack during the recursive traversal.

Code

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

        # swap the children
        tmp = root.left
        root.left = root.right
        root.right = tmp

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