# Leetcode – Invert Binary Tree Solution in Python

## Introduction

Inverting a binary tree, often dubbed as the “Reverse Engineering” of trees, is an elegant and classical problem in computer science. In this extensive article, we shall unravel the Invert Binary Tree problem on LeetCode, elucidate the conceptual understanding behind binary trees, and lay down various approaches to solve this problem in Python.

## Problem Statement

The Invert Binary Tree problem (LeetCode #226) is stated as follows:

Invert a binary tree.

Example: Input:

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


Output

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


This problem asks for the inversion of a binary tree, effectively mirroring it.

## Prerequisites

To invert a binary tree, it’s essential to understand the structure of a binary tree node. A binary tree is made up of nodes, where each node contains a left reference, a right reference, and a data element.

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

## Approach 1: Recursive Solution

In this approach, we will recursively swap the left and right children of all nodes in the tree.

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

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

# Invert the left and right subtrees
invertTree(root.left)
invertTree(root.right)

return root

This recursive approach has a time complexity of O(n), where n is the number of nodes in the tree, and a space complexity of O(h), where h is the height of the tree.

## Approach 2: Iterative Solution using a Queue (Breadth-First Search)

We can also solve this problem iteratively by using a queue. We will do a level order traversal and swap the left and right children of each node.

from collections import deque

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

queue = deque([root])

while queue:
current = queue.popleft()

# Swap the left and right subtrees
current.left, current.right = current.right, current.left

# Add the left and right children to the queue
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)

return root

This iterative approach also has a time complexity of O(n) and a space complexity of O(w), where w is the maximum width of the tree.

## Approach 3: Iterative Solution using a Stack (Depth-First Search)

Another iterative approach involves using a stack. This simulates the behavior of the recursive call stack.

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

stack = [root]

while stack:
current = stack.pop()

# Swap the left and right subtrees
current.left, current.right = current.right, current.left

# Add the right and left children to the stack
if current.left:
stack.append(current.left)
if current.right:
stack.append(current.right)

return root

This approach has the same time complexity of O(n), but with a space complexity of O(h), similar to the recursive approach.

## Testing the Solutions

Create a binary tree and pass it to the invertTree function to test the solutions.

# Creating a binary tree
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)

# Inverting the binary tree
inverted_tree = invertTree(root)

## Conclusion

Inverting a binary tree is a quintessential problem in computer science that challenges one’s understanding of tree data structures and traversal algorithms. Through recursive and iterative solutions, we have explored different strategies for tackling this problem efficiently.