AHU Canonical Encoding

Problem

Return the AHU canonical encoding string of an unrooted tree.

Root the tree at each minimum-degree candidate, encode every rooted tree bottom-up as sorted child encodings wrapped in parentheses, and take the lexicographically smallest encoding as the canonical form. edges is a list of [u, v] pairs. Return that string.

Hint

Using every minimum-degree node as a candidate covers the centers of the tree.

Test cases

case 1

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

expected: "(((())))"

case 2

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

expected: "((()()))"

case 3

in: [1,[]]

expected: "()"

case 4

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

expected: "(((()())))"

Starter codePython

def tree_ahu_canonical(n, edges):
    # Your code here
    pass

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