invert binary tree in python

Inverting a binary tree (also known as mirroring a binary tree) involves swapping the left and right children of all nodes in the tree. Here's a simple Python implementation for inverting a binary tree using a recursive approach, as well as an iterative approach using breadth-first traversal.

### Definition of the TreeNode class

First, you need a `TreeNode` class to represent each node in the tree:

```python
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
```

### Recursive Approach

Here is how you can invert a binary tree recursively:

```python
def invert_tree(root):
    if root is None:
        return None

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

    # Recursively call invert_tree on the children
    invert_tree(root.left)
    invert_tree(root.right)

    return root
```

### Iterative Approach (Using a Queue)

Here's how you can invert a binary tree using an iterative approach with a queue:

```python
from collections import deque

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

    queue = deque([root])
    
    while queue:
        current = queue.popleft()

        # Swap the children
        current.left, current.right = current.right, current.left

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

    return root
```

### Example Usage

Here's how you might use the above functions to invert a binary tree:

```python
# Helper function to print the tree in order (for testing)
def print_in_order(root):
    if root:
        print_in_order(root.left)
        print(root.value, end=' ')
        print_in_order(root.right)

# Create a sample binary tree
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Original tree (in order):")
print_in_order(root)
print("\nInverted tree (in order):")
inverted_root = invert_tree(root)
print_in_order(inverted_root)

# You can also use the iterative method
# inverted_root_iterative = invert_tree_iterative(root)
# print_in_order(inverted_root_iterative)
```

### Output
The printed output will show the original tree's traversal order and the inverted tree's traversal order, helping you verify the inversion.