How do I topologically sort a rooted tree from the "parentOf" relation?

27 views Asked by At

I have a N-node rooted tree whose nodes are labeled 0 through N-1. I am given the parentOf relation, that is, for each node i, parentOf[i] is the single node j such that j is the parent of i. I would like to sort the nodes of the tree from bottom to top. I've seen implementations of topological sort, but they are based on the inverse relation childrenOf. How do I implement the sort using the parentOf relation without explicitly inverting the relation?

Suppose that for the following tree:

                          0
                         / \
                        /   \
                       2     1
                            / \
                           /   \
                          3     4

We are given the parentOf array [-1,0,0,1,1], where the -1 indicates that node 0 has no parent. In that case we want to construct the topologically-sorted node list: [3,4,2,1,0], that is, nodes always appear before their parents.

Does this make sense?

0

There are 0 answers