In graph theory a tree is just any graph with no cycles. But in computer science we often use rooted trees. Rooted trees are like trees except they have one specific node as the "root", and all computation is done from the root.
The depth of a rooted tree is the smallest number, \$n\$, such that any node of the tree can be reached from the root in \$n\$ steps or less. If the root node is selected poorly and the depth is high this may mean that to get to certain nodes from the roots takes many steps.
Over time as we perform computation our rooted tree may change shapes so, we'd like to then "re-root" the tree. That is without changing the underlying tree change the root of the tree so that the resulting rooted tree has as low a depth as possible.
In this challenge you will be given as input a rooted tree with positive integers at every vertex. You should output the re-rooted tree. That is a tree which has it's root selected to minimize depth but is otherwise identical.
You may take input in any reasonable format but please state your format so your answers can be tested. You should take input and give output using the same format. The input will always have at least 1 node
This is code-golf so answers will be scored in bytes with the goal being to minimize the size of your source-code.
In the test cases we represent trees as a list of nodes. Each node is a tuple containing its value and a list of children represented as their indexes in the list. The root node is at index
This way of representing trees is not unique so if you use this format you may get output that is isomorphic to the given result but not identical.
[(1,),(9,),(5,)] -> [(9,[1,2]),(1,),(5,)] [(1,),(9,),(5,),(7,)] -> [(9,[1,2]),(1,),(5,),(7,)] or [(5,[1,3]),(9,),(1,),(7,)] [(1,),(8,[2,3]),(7,),(9,)] -> [(8,[1,2,3]),(1,),(7,),(9,)]