7
\$\begingroup\$

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.

Task

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 so answers will be scored in bytes with the goal being to minimize the size of your source-code.

Test Cases

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 0.

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,[1]),(9,[2]),(5,[])] -> [(9,[1,2]),(1,[]),(5,[])]
[(1,[1]),(9,[2]),(5,[3]),(7,[])] -> [(9,[1,2]),(1,[]),(5,[3]),(7,[])] or [(5,[1,3]),(9,[2]),(1,[]),(7,[])]
[(1,[1]),(8,[2,3]),(7,[]),(9,[])] -> [(8,[1,2,3]),(1,[]),(7,[]),(9,[])]
\$\endgroup\$
4
  • \$\begingroup\$ When there are multiple possible answers, may I still reroot it even the input already have a minimal height? \$\endgroup\$
    – tsh
    Jan 7 at 13:46
  • \$\begingroup\$ @tsh Yes. The output just needs to be minimal height. \$\endgroup\$
    – Wheat Wizard
    Jan 7 at 13:47
  • \$\begingroup\$ Is it necessary to output the whole tree again? If my tree is represented by an adjacency list and root index, then rerooting the tree doesn't change the list, so all I should need to output is the best root index. \$\endgroup\$
    – Neil
    Jan 7 at 17:44
  • \$\begingroup\$ @Neil I think it is necessary. In that format it's trivial to output the unchanged tree and so I don't see much difference between outputting it or not. But other formats may require more significant modification greatly changing the challenge if you only need to find the index. \$\endgroup\$
    – Wheat Wizard
    Jan 7 at 18:33
3
\$\begingroup\$

Wolfram Language (Mathematica), 63 bytes

GraphTree[g=UndirectedGraph@TreeGraph@#,Last@GraphCenter@g,#&]&

Takes input as a Tree object, e.g., Tree[1, {Tree[9, {Tree[5, None]}]}].

Tree objects are introduced in Mathematica 12.3, so no TIO.

Outputs for the test cases:

Tree[1, {Tree[9, {Tree[5, None]}]}] -> Tree[9, {Tree[1, None], Tree[5, None]}]
Tree[1, {Tree[9, {Tree[5, {Tree[7, None]}]}]}] -> Tree[9, {Tree[1, None], Tree[5, {Tree[7, None]}]}
Tree[1, {Tree[8, {Tree[7, None], Tree[9, None]}]}] -> Tree[8, {Tree[1, None], Tree[7, None], Tree[9, None]}]

Wolfram Language (Mathematica), 63 bytes

-3 bytes thanks to @att.

-(-#//.-a_[b___,c_@d___,e___]/;Depth@b?e<Depth@!d:>-b~a~e~c~d)&

Try it online!

Takes input as a Mathematica expression, e.g., 1[9[5[]]].

Outputs for the test cases:

1[9[5[]]] -> 9[1[], 5[]]
1[9[5[7[]]]] -> 9[1[], 5[7[]]]
1[8[7[], 9[]]] -> 8[1[], 7[], 9[]]

Or 59 bytes if we can take input as -1[9[5[]]] (I'm not sure if prepending a minus sign is a reasonable format. The output also has this minus sign):

#//.-a_[b___,c_@d___,e___]/;Depth@b?e<Depth@!d:>-b~a~e~c~d&

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -3 bytes on the second \$\endgroup\$
    – att
    Jan 7 at 18:55
2
\$\begingroup\$

Python3, 527 bytes:

from itertools import*
p=lambda x,i=0:[(x[i][0],x[j][0])for j in x[i][1]]+p(x,i+1)if i<len(x)else[]
d=lambda x,i=0:1+(max(d(x,l)for l in x[i][1])if x[i][1]else 0)
def f(n,p,c,u=[]):
 if not p:yield c
 else:
  if(x:=(i:=n.index)(p[0][0]))<(y:=i(p[0][1]))and y not in u:yield from f(n,p[1:],c[:x]+[(c[x][0],c[x][1]+[y])]+c[x+1:],u+[y])
  elif x not in u:yield from f(n,p[1:],c[:y]+[(c[y][0],c[y][1]+[x])]+c[y+1:],u+[x])
e=lambda x:min([j for k in permutations([i[0]for i in x],len(x))for j in f(k,p(x),[(i,[])for i in k])],key=d)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ al lot of small changes for -19 bytes Try it online! \$\endgroup\$
    – Jakque
    Jan 10 at 9:25
2
\$\begingroup\$

Charcoal, 60 59 bytes

≔EθEθ∨⁼κμ∨№η⟦κμ⟧№η⟦μκ⟧ζ≔EζιεW¬⊙ε⌊κUMεEκ⊙ζ∧§κπ§ξν⭆¹⟦θη⌕Eε⌊λ¹

Try it online! Link is to verbose version of code. I/O is a list of node values, an adjacency list and the root node. Explanation:

≔EθEθ∨⁼κμ∨№η⟦κμ⟧№η⟦μκ⟧ζ

Calculate the adjacency matrix.

≔Eζιε

Make a shallow clone we can safely mutate.

W¬⊙ε⌈κ

Until at one node can reach all the other nodes...

UMεEκ⊙ζ∧§κπ§ξν

... calculate the adjacency matrix for the next depth.

⭆¹⟦θη⌕Eε⌊λ¹

Output the original tree but with the new root node which the first node that can reach all the other nodes at the current depth.

\$\endgroup\$
1
\$\begingroup\$

JavaScript + DOM, 154 bytes

n=>R(D([R(D([n]))]).slice(P.length/2))
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c

Input a root HTMLElement. Output new root after re-root.

f=

n=>R(D([R(D([n]))]).slice(P.length/2))
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c

tree2Dom = ([name, children], parent = document.createElement('div')) => {
  parent.id = name;
  children.forEach(node => parent.append(tree2Dom(node)));
  return parent;
};
dom2Tree = node => [node.id, [...node.children].map(child => dom2Tree(child))];

testcases = [
['1', [['9', [['5', []]]]]],
['1', [['9', [['5', [['7', []]]]]]]],
['1', [['8', [['7', []], ['9', []]]]]],
];

testcases.forEach(t => {
  console.log(JSON.stringify(dom2Tree(f(tree2Dom(t)))));
});

With comment

// Find out the deepest element in root, output that element and all its parents
D=(h,...t)=>P=h&&D(...t,...[...h[0].children].map(x=>[x,...h]))||h
// Re-root the tree to c, input c and its parents
R=([c,...p])=>p[c.remove(),0]&&c.append(R(p))||c
// Find out the new root and re-root
n=>R(D([R(D([n]))]).slice(P.length/2))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.