Invert Binary Tree easy

Problem Statement

Invert a binary tree.

Example:

Input:

 4

/
2 7 / \ /
1 3 6 9

Output:

 4

/
7 2 / \ /
9 6 3 1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard.

Example 1

Input:

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

Output:

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

Example 2

Input:

   2
  / \
 1   3

Output:

   2
  / \
 3   1

Steps

1. Base Case: If the root is None, return None. This handles empty trees.

2. Recursive Step:

   • Swap the left and right children of the current node.
   • Recursively call the invertTree function on the new left child (which was originally the right child) and the new right child (which was originally the left child).

Explanation

The solution uses recursion. The base case stops the recursion when we reach a None node (an empty subtree). The recursive step performs the inversion at each node: it swaps the left and right subtrees. Because the function recursively calls itself on the swapped subtrees, the inversion propagates down the entire tree. This ensures that every node's children are swapped, effectively inverting the entire binary tree.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    """
    Inverts a binary tree.

    Args:
        root: The root node of the binary tree.

    Returns:
        The root node of the inverted binary tree.
    """
    if root is None:
        return None

    # Swap left and right children
    root.left, root.right = root.right, root.left

    # Recursively invert left and right subtrees
    root.left = invertTree(root.left)
    root.right = invertTree(root.right)

    return root

# Example usage:
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)

inverted_root = invertTree(root)

# Function to print the tree (for demonstration purposes)
def print_tree(node):
    if node:
        print(node.val)
        print_tree(node.left)
        print_tree(node.right)

print("Inverted Tree:")
print_tree(inverted_root)

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), the height can be equal to N. In the best case (a balanced tree), the height is log₂(N).