Leetcode 226 - Invert Binary Tree

Problem

Leetcode 226 - Invert Binary Tree

Example:

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]

Approach

For this problem, we can use a recursive approach to solve it. First, we check if the “root” is None, if so, we return None to indicate that the tree/subtree is empty. Then, we swap the left and right subtree of the root. Finally, we recursively call the function on the left and right subtree.

Visualization of the process:

root: 4
    4          
   / \
  2   7      
 / \ / \
1  3 6  9

Since root is not None, we swap the left and right subtree of the root.

    4
   / \
  7   2
 / \ / \
6  9 1  3

Now, we recursively call the function on the left and right subtree of the root.

root: 7
    7
   / \
  6   9

Since root is not None, we swap the left and right subtree of the root.

    7
   / \
  9   6

Now, we recursively call the function on the left and right subtree of the root.

root: 9
    9
   / \

Now, we recursively call the function on the left and right subtree of the root.

root: None

Since root is None, we return None.

root: 6
    6
   / \

Now, we recursively call the function on the left and right subtree of the root.

root: None

Since root is None, we return None.

Finally, we return the root.

    4
   / \
  7   2
 / \ / \
9  6 3  1

root: 2
    2
   / \
  1   3

Since root is not None, we swap the left and right subtree of the root.

    2
   / \
  3   1

Now, we recursively call the function on the left and right subtree of the root.

root: 3
    3
   / \      

Now, we recursively call the function on the left and right subtree of the root.

root: None

Since root is None, we return None.

root: 1
    1
   / \     

Now, we recursively call the function on the left and right subtree of the root.

root: None

Since root is None, we return None.

Finally, we return the root.

    4
   / \
  7   2
 / \ / \
9  6 3  1

We have successfully inverted the binary tree.

Here is the implementation of the approach:

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Base case: if the root is None, return None
        if not root:
            return None
        
        # Swap the left and right subtree of the root
        root.left, root.right = root.right, root.left
        
        # Recursively call the function on the left and right subtree of the root
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        # Return the root
        return root

Time Complexity and Space Complexity

Time Complexity: $O(n)$, where $n$ is the number of nodes in the tree. This is because we need to visit each node in the tree exactly once.

Space Complexity: $O(h)$, where $h$ is the height of the tree. This is because we need to store the call stack for the recursive function calls.