Tree Isomorphism AHU Canonical Form

Problem

Decide whether two unrooted trees are isomorphic using AHU canonical forms.

Root each tree at every minimum-degree candidate, encode each rooted tree bottom-up with sorted child encodings in parentheses, and take the lexicographically smallest encoding as the tree's canonical form. Return True when the two canonical forms are equal. n1, edges1, n2, edges2 describe the two trees.

Hint

Canonical parenthesized encodings make isomorphism a string comparison.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]],4,[[3,2],[2,1],[1,0]]]

expected: true

case 2

in: [4,[[0,1],[0,2],[0,3]],4,[[0,1],[1,2],[1,3]]]

expected: true

case 3

in: [3,[[0,1],[1,2]],3,[[0,1],[0,2]]]

expected: true

case 4

in: [4,[[0,1],[1,2],[2,3]],3,[[0,1],[1,2]]]

expected: false

Starter codePython

def tree_isomorphism(n1, edges1, n2, edges2):
    # Your code here
    pass

4 test cases · run your code against them in the editor