Binary tree isomorphism iterative

Question

I was wondering if there was a way to iteratively check if two binary trees were isomorphic to each other (in fact, we all know the problems with recursion), so far this is the best solution I've found: https://github.com/deepwritescode/isomorph#iterative.

However, I would like to remove the check condition on the value of the nodes; because what I need should be limited to checking the structure of the trees, instead of their actual values inside the nodes... Every language is accepted.

P.S.: this implementation doesn't work either: https://www.geeksforgeeks.org/iterative-approach-to-check-if-two-binary-trees-are-isomorphic-or-not/

Answer 1

To check if two trees (with value-less nodes) are isomorphic, you need to take into account that several nodes in the second tree may have their child trees reversed when compared to the first tree.

With a recursive algorithm you would need at least two recursive calls to be made at the same node, or more. The state in which these calls are made are different, and that state needs to be taken into account when rewriting it in an iterative way (and stack based).

Here is solution code in Python:

from dataclasses import dataclass

@dataclass
class Node:
    left: 'Node'=None
    right: 'Node'=None

@dataclass
class Item:
    n1: Node
    n2: Node 
    state: int


def isIsomorphic(n1, n2):
    stack = []
    item = Item(n1, n2, 0)
    
    while True:
        if not item.n1 and not item.n2:
            # success
            item.state = 4
            while item.state >= 2: # success
                if not stack:
                    return True
                item = stack.pop()
            item.state ^= 3
        elif not item.n1 or not item.n2:
            # failure
            item.state = 1
            while item.state >= 1: # failure
                if not stack:
                    return False
                item = stack.pop()
            item.state = 1
        # ... must push this and the corresponding children pair
        stack.append(item)
        item = Item(
            item.n1.right if item.state & 2 else item.n1.left, 
            item.n2.right if item.state & 1 else item.n2.left, 
            0
        )


# Create tree: just a shape, no values
root1 = Node(
    Node(
        Node(),
        Node(
            Node(),
            Node()
        )
    ),
    Node(
        Node(),
        None
    )
)
# Second tree - isomorph shape
root2 = Node(
    Node(
        Node(),
        None
    ),
    Node(
        Node(
            Node(),
            Node()
        ),
        Node()
    ),
)

print (isIsomorphic(root1, root2))  # True