Invert Binary Tree

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

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

As with all tree questions, we can use recursion to complete this question.

• First, for the base case, or the edge case of a single empty node. Here, there is nothing to invert, since its inverse is the same. Therefore we can return the tree without any changes.

• For a non-empty tree, we have to make sure two things are true:

  1. Its children are inverted and swapped.
  2. The subtrees are inverted.

  Since no descendant nodes cross over to the other side of the tree, we can treat the left and right subtree separately. Therefore, all we have to do is to invert the left and right subtrees, and then swap them.

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return root
    
    root.left, root.right = root.right, root.left
    self.invertTree(root.left)
    self.invertTree(root.right)

    return root

Time Complexity

Since every node must be inverted and each recursive call is constant time, we have $\mathcal{O}(n)$ time complexity.

Space Complexity

Since we don’t use any extra variables other than the input tree, we have constant space complexity.