Python – Calculates the height of an arbitrary (non-bifurcation) tree

I am currently studying the online data structure class (class), which is one of the homework; Please guide me to the answer, not give me the answer.

The hint is as follows:

Task. You are given a description of a rooted tree. Your task is to compute and output its height. Recall that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a leaf to the root. You are given an arbitrary tree, not necessarily a binary tree.

Input Format. The first line contains the number of nodes n. The second line contains integer numbers from −1 to n−1 parents of nodes. If the i-th one of them (0 ≤ i ≤ n−1) is −1, node i is the root, otherwise it’s 0-based index of the parent of i -th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree.

Constraints. 1 ≤ n ≤ 10⁵.

My current solution works, but very slow when n > 10². Here is my code :

# python3

import sys
import threading

# In Python, the default limit on recursion depth is rather low,
# so raise it here for this problem. Note that to take advantage
# of bigger stack, we have to launch the computation in a new thread.
sys.setrecursionlimit(10**7)  # max depth of recursion
threading.stack_size(2**27)   # new thread will get stack of such size
threading. Thread(target=main).start()

# returns all indices of item in seq
def listOfDupes(seq, item):
    start = -1
    locs = []
    while True:
        try:
            loc = seq.index(item, start+1)
        except:
            break
        else:
            locs.append(loc)
            start = loc
    return locs

def compute_height(node, parents):
    if node not in parents:
        return 1
    else:
        return 1 + max(compute_height(i, parents) for i in listOfDupes(parents, node))

def main():
    n = int(input())
    parents = list(map(int, input().split()))
    print(compute_height(parents.index(-1), parents))

Example input:
>>> 5
>>> 4 -1 4 1 1
This will result in a solution of 3 because the roots are 1, 3, and 4 branches 1, and then 0 and 2 branch out from 4, which makes the tree a height of 3

How can I improve this code to make it under a 3-second time benchmark? Also, would it be easier in another language?

As long as the algorithm is correct, Python will do. Since you’re just looking for guidance, consider:

1) If we know the depth of the parent node, we know the depth of the node; and
2) We are not interested in the structure of the tree, so we can discard irrelevant information.

The value of the root node pointer is -1. Suppose we replace its child pointer to the root node with the value -2, their child pointer with -3, and so on. The largest absolute of these is the height of the tree.

If we traverse the tree from any node N(0), we can stop as soon as node N(k) encounters a negative value, at which point we can replace each node with the value of its parent node, subtracting one. That is, N(k-1) = N(k) -1, N(k-2) = N(k-1) – 1 … N(0) = N(1) -1。 As more and more pointers are replaced by their depth, each traversal is more likely to terminate by encountering nodes of known depth. In fact, this algorithm is basically linear time.

So: load the data into an array, iterating through the pointer from the first element until a negative value is encountered. Build another traversed array of nodes. When negative values are encountered, use the second array to replace the original values in the first array with their depth. Do the same for the second element, and so on. Track the maximum depth you encounter: that’s your answer.