Compare nested lists

"""
Two lists, the elements in the list are either strings or lists, such as [a, [b, [c]], [d]].
Give you two such lists to judge whether their contents are the same, REGARDLESS OF ELEMENT ORDER.
"""

### STEP 1 ###
class Node:
    def __init__(self, val: str = "", children = {}):
        self.val = val
        self.children = children

    def create_child(self, other_node):
        if other_node.val in self.children:
            return
        self.children[other_node.val] = other_node
        return

### STEP 2 ###
def solve(nested_list1: list[str | list], nested_list2: list[str | list]) -> bool:
    ### STEP 2 ###
    root1 = build_tree(nested_list1)
    root2 = build_tree(nested_list2)

    ### STEP 4 -- YOU HAVE OPTIONS! ###
    answer1 = compare(root1, root2)
    answer = compare_bfs(root1, root2) # MAIN
    assert answer == answer1

    ### STEP 5 ###
    return answer

### STEP 3 ###
def build_tree(nested_list: list[str | list]) -> 'root Node':
    """
    Time Complexity: O(nlogn) -- n = number of elements if 'nested list' flattened
    Space Complexity: O(n)    -- n = number of elements if 'nested list' flattened
    """

    next_root_chars = []; next_nested_lists = []
    for element in nested_list:
        if isinstance(element, str):
            next_root_chars.append(element)
        else:
            next_nested_lists.append(element)

    next_root_chars.sort()
    next_child_nodes = [build_tree(element) for element in next_nested_lists]

    root = Node(val = ",".join(next_root_chars), children = {node.val: node for node in next_child_nodes})
    return root

### STEP 4
def compare(root1: "Node", root2: "Node") -> bool:
    """
    Time Complexity: O(n) -- n = number of elements if 'nested list' flattened
    Space Complexity: O(n)    -- n = number of elements if 'nested list' flattened
    """
    if (not root1) or (not root2):
        return (not root1) and (not root2)

    if root1.val != root2.val:
        return False

    answer = True
    shorter_map = root1.children if len(root1.children) < len(root2.children) else root2.children
    longer_map = root2.children if len(root1.children) < len(root2.children) else root1.children
    for next_val in shorter_map:
        if next_val not in longer_map:
            return False
        answer &= compare(root1.children[next_val], root2.children[next_val])

    return answer

def compare_bfs(root1, root2) -> bool:
    """
    Use queue because the nested list
    can be extremely deep, leading stack overflow.

    Time Complexity: O(n) -- n = number of elements if 'nested list' flattened
    Space Complexity: O(n)    -- n = number of elements if 'nested list' flattened
    """
    from collections import deque

    queue = deque([(root1, root2)])
    while queue:
        node1, node2 = queue.popleft()

        if (not node1) or (not node2):
            if (not node1) and (not node2):
                continue
            else:
                return False

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

        shorter_map = node1.children if len(node1.children) < len(node2.children) else node2.children
        longer_map = node2.children if len(node1.children) < len(node2.children) else node1.children

        for next_val in shorter_map:
            if next_val not in longer_map:
                return False
            queue.append((node1.children[next_val], node2.children[next_val]))

    return True

### STEP 6 ###
assert solve(["abc"], ["bac"]) == False
assert solve(["abc"], ["abc"]) == True

assert solve(["b", "a"], ["a", "b"]) == True
assert solve([["a"], "b", "c"], ["a", "b", "c"]) == False
assert solve([["a", "b"], "c"], ["c", ["b", "a"]]) == True

assert solve(['a', ['b', ['c']], 'd'], ['d', ['b', ['c']], 'a']) == True
assert solve(['a', ['b', ['c']], ['d']], ['d', ['b', ['c']], 'a']) == False
assert solve(['a', ['b', ['c']], ['d']], ['d', ['b', ['c']]]) == False