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?