Checking Tree Isomorphism by Swapping Nodes: Python Approaches

by

💡 Problem Formulation: Imagine you have two binary trees, and you want to determine if one tree can be transformed into the other simply by swapping left and right child nodes at any number of nodes. This article guides you through five methods to ascertain whether two trees are isomorphic in this way, using Python. For example, if the input binary trees are T1 and T2, and by swapping certain nodes in T1 we can form T2, the program would output True.

Method 1: Recursive Traversal

This method involves checking each node recursively to see if swapping its children can make the two trees identical. The function will compare each corresponding node and decide whether to swap or not based on the similarity of the sub-trees.

Here’s an example:

def areIsomorphic(n1, n2): 
    if n1 is None and n2 is None: 
        return True
    if n1 is None or n2 is None: 
        return False
    if n1.data != n2.data: 
        return False
    return (areIsomorphic(n1.left, n2.left) and
            areIsomorphic(n1.right, n2.right)) or 
           (areIsomorphic(n1.left, n2.right) and 
            areIsomorphic(n1.right, n2.left))

Output True or False depending on whether the trees can be formed by swapping nodes.

This recursive function forms the heart of our comparison, systematically digging into each tree and checking all possibilities of swaps at each node. It is elegant but may suffer from a performance drawback with highly unbalanced trees or trees with many nodes due to its recursive nature.

Method 2: Iterative Level-Order Traversal

This approach uses an iterative level-order traversal (using a queue) to compare the nodes of the two trees. It checks if for any node, a swap of its children nodes could make the corresponding subtrees equal.

Here’s an example:

from collections import deque

def areIsomorphicIterative(n1, n2):
    if n1 is None and n2 is None:
        return True
    if n1 is None or n2 is None:
        return False
    queue = deque([(n1, n2)])
    while queue:
        node_pair = queue.popleft()
        if node_pair[0].data != node_pair[1].data:
            return False
        left = (node_pair[0].left, node_pair[1].left)
        right = (node_pair[0].right, node_pair[1].right)
        queue.append(left)
        queue.append(right)
    return True

Output True or False accordingly.

This method circumvents the stack overflow issue that can occur with deep recursion by using an iterative approach, potentially offering better performance on large trees.

Method 3: Hashing Subtrees

By hashing the structure and values of the subtrees, we can compare large structures with a single hash comparison. This method involves creating a hash for each subtree and then comparing these hashes for the two trees at each level.

Here’s an example:

# This is a conceptual method. Hashing function should be implemented
def hash_tree(node):
    if node is None: return hash(None)
    return hash((node.data, hash_tree(node.left), hash_tree(node.right)))

def areIsomorphicWithHash(n1, n2):
    return hash_tree(n1) == hash_tree(n2)

Output True or False, based on hash comparison.

This code snippet assumes an ideal hashing function which could potentially give a fast answer. However, in real cases, the hash function must be chosen carefully to avoid collisions that would yield incorrect results.

Method 4: Dynamic Programming with Memoization

Dynamic programming can improve efficiency by storing results of sub-problems (subtrees comparisons in this case) and reusing them. This avoids recomputing results for subtrees that have already been compared.

Here’s an example:

memo = {}

def areIsomorphicDP(n1, n2):
    if (n1, n2) in memo:
        return memo[(n1, n2)]
    if n1 is None and n2 is None: 
        memo[(n1, n2)] = True
    elif n1 is None or n2 is None: 
        memo[(n1, n2)] = False
    elif n1.data != n2.data: 
        memo[(n1, n2)] = False
    else:
        memo[(n1, n2)] = (areIsomorphicDP(n1.left, n2.left) and
                         areIsomorphicDP(n1.right, n2.right)) or 
                        (areIsomorphicDP(n1.left, n2.right) and 
                         areIsomorphicDP(n1.right, n2.left))
    return memo[(n1, n2)]

Output True or False as per the memoized results.

The memoization strategy saves previous computations and retrieval is fast once a subtree comparison is memoized. This method is powerful, but the memory overhead may be substantial with a big tree.

Bonus One-Liner Method 5: Using External Libraries

Python has a rich ecosystem of libraries. We can leverage an external library like networkx to model the trees as graphs and then apply existing algorithms for graph isomorphism—a process analogous to checking if two trees can be formed by swapping nodes.

Here’s an example:

import networkx as nx

# Assumed trees are converted to NetworkX graphs as g1 and g2
def areIsomorphicLib(g1, g2):
    return nx.is_isomorphic(g1, g2, node_match=lambda n1, n2: n1['data'] == n2['data'])

Output True or False depending on whether the graphs (trees) are isomorphic.

This external library implementation can be very efficient, especially if the library is well-optimized. However, it introduces additional dependencies and may complicate the environment.

Summary/Discussion

  • Method 1: Recursive Traversal. Simple to implement. It can be slow for large or unbalanced trees due to recursive calls.
  • Method 2: Iterative Level-Order Traversal. Avoids stack overflow and can handle large trees better. However, it requires careful management of the queue.
  • Method 3: Hashing Subtrees. Potentially fast with a good hash function. However, it is prone to collisions.
  • Method 4: Dynamic Programming with Memoization. Great performance on repetitive subtree comparisons. Memory-intensive for large trees.
  • Bonus Method 5: Using External Libraries. Can be very efficient with well-optimized libraries but adds dependency overhead.