20. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root. Inverting a binary tree means swapping every left child with its corresponding right child.

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Input: root = [2,1,3]
Output: [2,3,1]

Input: root = []
Output: []

Problem Breakdown:

1. Base case: if the node is null, return null. This handles empty trees and leaf node children.

• if not root:
      return None

2. Swap the left and right children of the current node. This is the core operation of inverting.

• root.left, root.right = root.right, root.left

3. Recursively invert the left subtree and the right subtree. After swapping, each subtree also needs to be inverted.

• invertTree(root.left)
  invertTree(root.right)

4. Return the root node. The entire tree below this node has been inverted.

• return root

Summary:

Recursively swap left and right children at every node. The base case is a null node. After swapping children at the current level, recursively invert both subtrees. The tree is inverted from top to bottom.

Time and Space Complexity:

Time Complexity: O(n) - we visit every node once.

Space Complexity: O(h) - where h is the height of the tree, due to recursion stack. O(n) worst case for skewed trees.

Python Solution:

def invertTree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

JavaScript Solution:

var invertTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

Java Solution:

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}