A binary tree is a fundamental data structure in computer science, where each node has at most two children, often referred to as the left child and the right child. Understanding and manipulating binary trees are crucial for various algorithmic applications, including searching and sorting operations, as well as in more complex structures like binary search trees and heap data structures. One interesting operation on binary trees is the creation of their "mirror image." This article explores the concept of the mirror image of a binary tree, explaining how it is formed, its applications, and how it can be implemented.

Understanding the Mirror Image of a Binary Tree

The mirror image of a binary tree refers to a new binary tree obtained by swapping the left and right children of all the nodes in the original tree. If $T$ is a binary tree, its mirror image $T'$ is such that for every node in $T$, the left and right subtrees are replaced.

Example

Consider the following binary tree:

1    1
2   / \
3  2   3
4 / \
54   5

The mirror image of this tree would be:

1    1
2   / \
3  3   2
4     / \
5    5   4

In the mirror image, the left and right children of the root node and the node labeled '2' are swapped.

Algorithm for Creating Mirror Image

Creating a mirror image of a binary tree can be done recursively or iteratively.

Recursive Approach

The recursive approach involves a depth-first traversal where you swap the left and right children at every node. The procedure is as follows:

1. Base Condition: If a node is null, return as there's nothing to swap.
2. Recursive Work:
   • Recursively find the mirror image of the left and right subtrees.
   • Swap the left and right children of the current node.

Here's a simple recursive implementation in Python:

1class TreeNode:
2    def __init__(self, value=0, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7def mirror_tree(node):
8    if node is None:
9        return
10    
11    # Swap the left and right subtrees
12    node.left, node.right = node.right, node.left
13    
14    # Recurse on the left and right subtrees
15    mirror_tree(node.left)
16    mirror_tree(node.right)

Iterative Approach

An iterative approach can use a queue or stack to traverse the tree in a breadth-first or depth-first manner while swapping nodes:

1. Initialize a queue and enqueue the root node.
2. While the queue is not empty:
   • Dequeue a node.
   • Swap its left and right children.
   • Enqueue the non-null left and right children for further processing.

1from collections import deque
2
3def mirror_tree_iterative(root):
4    if root is None:
5        return
6    
7    queue = deque([root])
8
9    while queue:
10        current = queue.popleft()
11        
12        # Swap the children
13        current.left, current.right = current.right, current.left
14        
15        # Enqueue the non-null children
16        if current.left:
17            queue.append(current.left)
18        if current.right:
19            queue.append(current.right)

Applications

1. Symmetry Verification: Determine if a binary tree is symmetric around its center.
2. Image Processing: Used in graphical transformations where spatial coordinate systems are inverted.
3. Data Reconstruction: Useful in reconstructing data structures in reverse order.

Comparison

Here's a brief comparison of the recursive and iterative approaches:

Conclusion

Creating a mirror image of a binary tree is a fundamental operation that swaps the left and right subtrees of each node, effectively creating a new tree that is a "reflection" of the original. The mirror image plays a vital role in various applications, including algorithmic problems related to tree symmetry and graphical processing. Both recursive and iterative approaches have their merits, and selecting the right one depends on the specific use case and constraints such as memory and ease of implementation.