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.