Data Structures and Algorithms: Check if Tree is Mirror 🌳💡

Welcome to today's lesson on Data Structures and Algorithms! Today, we'll dive into an interesting problem: Checking if a Tree is Mirror. This lesson is perfect for both beginners and intermediates, so let's get started!

Table of Contents 📝

What is a Tree?
Understanding Mirror Trees
Algorithm to Check if a Tree is Mirror
- Recursive Approach
- Iterative Approach
Code Examples
Quiz

What is a Tree? 🌳📝

A tree is a data structure that represents a hierarchical set of objects. It consists of nodes connected by edges, where each node (except for the root node) has exactly one parent node and can have zero or more child nodes.

Here's a simple example of a tree:

   A
  / \
 B   C
  \   \
   D   E

In this example, A is the root node, B, C, D, and E are the child nodes, and B and C are the siblings of each other.

Understanding Mirror Trees 💡

A mirror tree (or symmetric tree) is a binary tree where the left subtree of every node is a mirror image of the right subtree. In other words, if we swap the left and right subtrees of every node, we get the mirror tree.

Here's an example of a mirror tree:

In this example, if we swap the left and right subtrees of each node, we get the mirror tree.

Algorithm to Check if a Tree is Mirror 💡

There are two common approaches to check if a tree is a mirror tree:

Recursive Approach
Iterative Approach

Recursive Approach 🎯

The recursive approach involves checking the mirror condition at each level of the tree. To check if a tree is a mirror tree, we call a helper function that checks the left and right subtrees recursively. If both the subtrees are mirror images of each other and the root values of both sides are the same, then the tree is a mirror tree.

Here's a recursive function for checking if a tree is a mirror tree:

python

def is_mirror(node1, node2):
    # If both nodes are None, the trees are identical (empty)
    if not node1 and not node2:
        return True

    # If one node is None and the other isn't, the trees are not identical
    if not node1 or not node2:
        return False

    # If the values of both nodes don't match, the trees are not identical
    if node1.data != node2.data:
        return False

    # Recursively check the left and right subtrees
    return is_mirror(node1.left, node2.right) and is_mirror(node1.right, node2.left)

Iterative Approach 🎯

The iterative approach uses a stack to traverse the tree. We keep track of the left and right subtrees separately and check if they are mirror images of each other at each level.

Here's an iterative function for checking if a tree is a mirror tree:

python

def is_mirror(root):
    # Use a stack to traverse the tree
    stack = [(root, None)]

    while stack:
        node1, node2 = stack.pop()

        # If the nodes are not identical, the trees are not mirror
        if not node1 and node2:
            return False
        if node1 and not node2:
            return False
        if node1.data != node2.data:
            return False

        # Swap the left and right subtrees for the next level
        stack.append((node1.right, node2.left))
        stack.append((node1.left, node2.right))

    # If we reach here, the trees are mirror images of each other
    return True

Code Examples 💡

Let's see the recursive and iterative approaches in action with a simple example:

python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def create_tree():
    a = Node('A')
    b = Node('B')
    c = Node('C')
    d = Node('D')
    e = Node('E')

    a.left = b
    a.right = c
    b.left = d
    b.right = e

    return a

def is_mirror_recursive(node1, node2):
    return is_mirror(node1, node2, None, None)

def is_mirror_iterative(root):
    return is_mirror(root, None)

root = create_tree()
print(is_mirror_recursive(root, root))  # True

Quiz 🎯

Now that you've learned about mirror trees and seen the recursive and iterative approaches, let's test your knowledge with a quiz!