Invert Binary Tree

The problem description can be found in LeetCode.

Approach

This is our first Tree problem. They can be quite tricky at first and it takes time to master them.

What can we notice from the examples?

Surely, the root node remains the same, which means that we must return the root node itself, but we have to apply some logic before.

This logic is quite simple: just switch the left and right, and, after doing so, we can apply the same logic recursively to the children nodes.

Solution

from typing import Optional


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

Complexity

• Time: $O(n)$
• Space: $O(h)$

Where $n$ is the number of nodes in the tree and $h$ is its height. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.