Given a rooted tree with N nodes, what nodes are leaves?
A leaf is a node with no children when we walk down the tree from the root node (the Don).
We are given a list R of N integers, where element R_i denotes to whom person i reports to.
For every person P, we want to know if there is any other person reporting to P.
A simple approach is: for every person i, search the given list to see if anyone reports to i.
for i from 1 to N do for j from 1 to N do if R[i] equals i then person j reports to i and is not a leaf if person i does not have any reports, add to solution
For every person, we do a linear scan on the given list. It’s clear that the time complexity of this approach is O(N^2) which was enough for the first subtask but not for the second.
We can do better. We really just want to know for every person P if there is anyone that reports to P.
There are several ways to do this efficiently. A simple way is to use a boolean array, e.g. has_reports, and use this to store if node i has anyone reporting to it. We can process the given list only once and mark has_reports[i] to true when someone reports to i. Sample pseudo-code:
Initialise has_reports array to false in all positions for i from 1 to N do has_children[R[i]] = true for i from 1 to N do if has_children[i] is true then print i
We only process the list once and use an array to mark the reports information. So the time complexity of this approach is O(N). Also, the space complexity is O(N).