Centroid Decomposition Pick

Problem

Find the centroid of a tree given by a parent array.

parents[i] is the parent of node i (-1 for the root). The centroid minimizes the largest remaining component when removed; ties go to the smallest index.

Return the centroid node.

Hint

The centroid's largest component is at most half the tree, and it is unique up to ties.

Test cases

case 1

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

expected: 2

case 2

in: [[-1,0,0,0,0]]

expected: 0

case 3

in: [[-1,0]]

expected: 0

case 4

in: [[-1]]

expected: 0

case 5

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

expected: 0

Starter codePython

def find_centroid(parents):
    # Your code here
    pass

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