Find depth of a k-ary tree given a parent array : Solution 2

The problem statement is mentioned here. The first solution is here.

We can reduce some processing by observation that we only need to find the depth of leaf nodes. Any node whose index appears in the parent array $P$ is an internal node and do not need to be processed. The modified solution is as below:

Let L be an array of length N
Initialize all elements of L to true
for each node i from 0 to N-1
   if P[i] is not -1
       set L[P[i]] to false
   end if
end for
initialize maxDepth to 0
for each node i from 0 to N-1
    if L[i] is false, continue next node
    set parent to P[i]
    set depth to 1
    while parent is not -1
       set parent to P[parent]
       increment depth
    end while
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N^2)$ where $N$ is the number of nodes. Thus the worst case is still not improved. The space complexity is $O(N)$.