.png)
[JOIN OUR BLOG] for daily coding insights
DSA Series Chapter 25 : MIRROR OF BINARY TREE(Python Version)
1. Objective
To convert a given binary tree into its mirror image by recursively swapping the left and right subtrees of every node using Python.
2. Definition (Exam-Ready)
The mirror of a binary tree is a tree in which the left and right children of all nodes are interchanged.
3. Example
Original Binary Tree
1
/ \
2 3
/ \
4 5
Mirror Binary Tree
1
/ \
3 2
/ \
5 4
4. Key Observation
Mirroring is a structural transformation
Node data remains unchanged
Only references (links) are swapped
5. Core Logic (Recursive)
For each node:
Swap left and right children
Recursively mirror left subtree
Recursively mirror right subtree
6. Recursive Formula
mirror(node) =
return if node is None
swap(node.left, node.right)
mirror(node.left)
mirror(node.right)
7. Binary Tree Node Class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
8. Function to Mirror Binary Tree
def mirror_tree(root):
if root is None:
return
root.left, root.right = root.right, root.left
mirror_tree(root.left)
mirror_tree(root.right)
9. Line-by-Line Explanation
if root is None:
return
Base case
Empty subtree needs no mirroring
root.left, root.right = root.right, root.left
Swaps left and right child references
mirror_tree(root.left)
mirror_tree(root.right)
Recursively mirrors both subtrees
10. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def mirror_tree(root):
if root is None:
return
root.left, root.right = root.right, root.left
mirror_tree(root.left)
mirror_tree(root.right)
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Inorder traversal before mirroring:")
inorder(root)
mirror_tree(root)
print("\nInorder traversal after mirroring:")
inorder(root)
11. Output
Inorder traversal before mirroring:
4 2 5 1 3
Inorder traversal after mirroring:
3 1 5 2 4
12. Time and Space Complexity
Time Complexity
O(n)
Every node is visited exactly once.
Space Complexity
O(h) due to recursion stack
(h = height of tree)
13. Important Exam Points
Mirror operation affects structure, not values
Recursive solution is most common
Inorder traversal changes after mirroring
Preorder root remains unchanged
14. Common Beginner Mistakes
Swapping node data instead of links
Forgetting base case
Assuming only leaf nodes change
Calling recursion before swap
15. Learning Outcome
After completing this post, learners can:
Visualize mirror transformation
Implement mirror operation in Python
Analyze traversal changes after mirroring
Answer exam and interview questions confidently
Comments
Post a Comment