Invert Binary Tree - Python Solution

1. Introduction

"Invert Binary Tree" is a popular problem in the domain of binary trees, often seen in coding interviews and algorithm challenges. The task involves flipping a binary tree, effectively swapping the left and right children of all nodes in the tree. This problem is a great exercise in understanding tree traversal and manipulation.

Problem

Given the root of a binary tree, the objective is to invert the tree, such that each node's left child becomes its right child and vice versa, and then return the root of the inverted tree.

2. Solution Steps

1. Traverse the tree using a depth-first approach.

2. At each node, swap its left and right children.

3. Apply this swapping recursively to all nodes in the tree.

4. Continue the process until every node has been visited and swapped.

5. Return the root of the now inverted tree.

3. Code Program

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

def invertTree(root):
    if not root:
        return None

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

    # Recursively invert the subtrees
    invertTree(root.left)
    invertTree(root.right)

    return root

# Example Usage
root = TreeNode(4)
root.left = TreeNode(2, TreeNode(1), TreeNode(3))
root.right = TreeNode(7, TreeNode(6), TreeNode(9))
invertTree(root)

Output:

The binary tree is inverted, with each node's left and right children swapped.

Explanation:

1. Recursive Function: invertTree inverts a binary tree by recursively traversing it.

2. Node Swapping: At each node, the function swaps its left and right children.

3. Recursion: The process is applied recursively to both the left and right subtrees.

4. Base Case: The recursion stops when a null node is encountered.

5. Inverted Tree: The function returns the root of the inverted tree, with the structure of the tree completely mirrored.