# PROBLEM LINK:

**Author:** Maksym Bevza

**Tester:** Istvan Nagy

**Editorialist:** Miguel Oliveira

# DIFFICULTY:

Cakewalk

# PREREQUISITES:

None

# PROBLEM:

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

# EXPLANATION:

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.

## Subtask1

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.

## Subtask 2

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