Binary Tree Mirror
A binary tree mirror refers to the process of creating a new binary tree where the left and right children of each node are swapped. This operation results in a new binary tree that is the mirror image of the original tree.
Example: Let's create a binary tree and perform the mirror operation on it.
# Node class definition
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Print the original tree
def print_tree(node):
if node is None:
return
print(node.value)
print_tree(node.left)
print_tree(node.right)
print("Original Tree:")
print_tree(root)
# Output:
# 1
# 2
# 4
# 5
# 3
# Mirror the binary tree
def mirror_tree(node):
if node is None:
return None
# Swap left and right children
node.left, node.right = node.right, node.left
# Recursively mirror the left and right subtrees
mirror_tree(node.left)
mirror_tree(node.right)
return node
# Mirror the tree
mirror_root = mirror_tree(root)
# Print the mirror tree
print("Mirror Tree:")
print_tree(mirror_root)
# Output:
# 1
# 3
# 2
# 5
# 4
In this example, we define a Node
class that represents a node in the binary tree. Each node has a value, left child, and right child.
We create a binary tree with the given values. The original tree is printed using a recursive function print_tree
.
To mirror the binary tree, we define a function mirror_tree
that takes a node as an argument. In this function, we swap the left and right children of the current node using a simultaneous assignment. Then, we recursively call mirror_tree
on the left and right children to mirror their respective subtrees. Finally, we return the modified node.
After mirroring the tree, we print the mirror tree using the print_tree
function.
Let's solve a question using the concept of a binary tree mirror. The question is "Symmetric Tree," which requires checking if a binary tree is symmetric.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class Solution:
def is_symmetric(self, root):
def is_mirror(node1, node2):
if node1 is None and node2 is None:
return True
if node1 is None or node2 is None:
return False
return (node1.value == node2.value and
is_mirror(node1.left, node2.right) and
is_mirror(node1.right, node2.left))
if root is None:
return True
return is_mirror(root.left, root.right)
# Create an instance of Solution
solution = Solution()
# Create a symmetric tree
root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)
# Check if the tree is symmetric
print(solution.is_symmetric(root))
# Output: True
# Create a non-symmetric tree
root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.right = Node(3)
root.right.right = Node(3)
# Check if the tree is symmetric
print(solution.is_symmetric(root))
# Output: False
In this solution, we define a Node
class to represent a node in the binary tree. We also define a Solution
class that contains the is_symmetric
method to check if a given binary tree is symmetric.
The is_symmetric
method uses a recursive helper function is_mirror
to check if the left and right subtrees are mirrors of each other. The is_mirror
function takes two nodes as arguments and performs the following checks:
- If both nodes are
None
, they are mirrors (base case). - If only one of the nodes is
None
, they are not mirrors. - Check if the values of the nodes are equal and if the left subtree of the first node is a mirror of the right subtree of the second node, and vice versa.
The is_symmetric
method returns True
if the root is None
(an empty tree) or if the left and right subtrees are mirrors. Otherwise, it returns False
.
The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(n) in the worst case, as the recursion stack may grow up to the number of nodes in the tree.