Check if Two Trees are Identical

Tree data structures are fundamental in computer science, used extensively in various applications. Often, you’ll need to determine if two trees are structurally identical – meaning they have the same node values arranged in the same way. This blog post explores efficient Pythonic ways to achieve this.

Understanding Tree Structure

Before diving into the code, let’s clarify what we mean by “identical trees.” Two trees are considered identical if:

1. Both are empty: If both trees have no nodes, they are identical.
2. Both have the same data: The root nodes of both trees must contain the same data.
3. Their left and right subtrees are identical: This recursively applies to every node in the tree.

Recursive Approach

The most intuitive and elegant method to compare trees is using recursion. This approach uses the self-similar nature of trees.

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

def areIdentical(root1, root2):
    # Base Case: Both trees are empty
    if root1 is None and root2 is None:
        return True

    # Base Case: One tree is empty, the other is not
    if root1 is None or root2 is None:
        return False

    # Check if data of nodes is equal
    if root1.data != root2.data:
        return False

    # Recursively check left and right subtrees
    return (areIdentical(root1.left, root2.left) and
            areIdentical(root1.right, root2.right))

# Example usage:
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)

root2 = Node(1)
root2.left = Node(2)
root2.right = Node(3)

root3 = Node(1)
root3.left = Node(2)
root3.right = Node(4) #Different from root1 and root2


print(f"Are root1 and root2 identical? {areIdentical(root1, root2)}") # Output: True
print(f"Are root1 and root3 identical? {areIdentical(root1, root3)}") # Output: False

This recursive function elegantly handles the base cases (empty trees) and recursively compares nodes and their subtrees.

Iterative Approach using Queues

While recursion is clear, an iterative approach using a queue can be advantageous for very deep trees to avoid potential stack overflow errors.

from collections import deque

def areIdenticalIterative(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False

    queue1 = deque([root1])
    queue2 = deque([root2])

    while queue1 and queue2:
        node1 = queue1.popleft()
        node2 = queue2.popleft()

        if node1.data != node2.data:
            return False

        if (node1.left is None and node2.left is not None) or \
           (node1.left is not None and node2.left is None) or \
           (node1.right is None and node2.right is not None) or \
           (node1.right is not None and node2.right is None):
            return False

        if node1.left:
            queue1.append(node1.left)
        if node2.left:
            queue2.append(node2.left)
        if node1.right:
            queue1.append(node1.right)
        if node2.right:
            queue2.append(node2.right)

    return not queue1 and not queue2 #Both queues should be empty if identical


#Example Usage (same trees as above)
print(f"Are root1 and root2 identical (iterative)? {areIdenticalIterative(root1, root2)}") # Output: True
print(f"Are root1 and root3 identical (iterative)? {areIdenticalIterative(root1, root3)}") # Output: False

This iterative version uses two queues to process nodes level by level, ensuring correctness and avoiding potential stack overflow issues with deep trees. Note the careful handling of None values to ensure proper comparison.

Choosing the Right Approach

Both the recursive and iterative approaches are valid. The recursive solution is often considered more concise and readable for simpler cases, while the iterative solution might be preferred for very large or deeply nested trees to prevent potential stack overflow errors. The best choice depends on the specific application and the expected size of the trees.