Time limit exceeded when finding tree height

this is my code to find the height of a tree of up to 10^5 nodes. May I know why I get the following error?

Warning, long feedback: only the beginning and the end of the feedback message is shown, and the middle was replaced by ” … “. Failed case #18/24: time limit exceeded

Input: 100000

Your output: stderr: (Time used: 6.01/3.00, memory used: 24014848/2147483648.)

Is there a way to speed up this algo?

This is the exact problem description:

Problem Description 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 𝑛. The second line contains 𝑛 integer numbers from −1 to 𝑛 − 1 — parents of nodes. If the 𝑖-th one of them (0 ≤ 𝑖 ≤ 𝑛 − 1) is −1, node 𝑖 is the root, otherwise it’s 0-based index of the parent of 𝑖-th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree.

Constraints. 1 ≤ 𝑛 ≤ 105

Output Format. Output the height of the tree.

# python3

import sys, threading
from collections import deque, defaultdict
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size

class TreeHeight:
        def read(self):
                self.n = int(sys.stdin.readline())
                self.parent = list(map(int, sys.stdin.readline().split()))

        def compute_height(self):
                height = 0
                nodes = [[] for _ in range(self.n)]
                for child_index in range(self.n):
                        if self.parent[child_index] == -1:
                                # child_index = child value
                                root = child_index
                                nodes[0].append(root)
                        # do not add to index
                        else:
                                parent_index = None
                                counter = -1
                                updating_child_index = child_index
                                while parent_index != -1:
                                        parent_index = self.parent[updating_child_index]
                                        updating_child_index = parent_index
                                        counter += 1
                                nodes[counter].append(child_index)
                                # nodes[self.parent[child_index]].append(child_index)
                nodes2 = list(filter(lambda x: x, nodes))
                height = len(nodes2)
                return(height)
                
               
def main():
  tree = TreeHeight()
  tree.read()
  print(tree.compute_height())

threading.Thread(target=main).start()

Answer

First, why are you using threading? Threading isn’t good. It is a source of potentially hard to find race conditions and confusing complexity. Plus in Python, thanks to the GIL, you often don’t get any performance win.

That said, your algorithm essentially looks like this:

for each node:
    travel all the way to the root
    record its depth

If the tree is entirely unbalanced and has 100,000 nodes, then for each of 100,000 nodes you have to visit an average of 50,000 other nodes for roughly 5,000,000,000 operations. This takes a while.

What you need to do is stop constantly traversing the tree back to the root to find the depths. Something like this should work.

import sys

class TreeHeight:
    def read(self):
        self.n = int(sys.stdin.readline())
        self.parent = list(map(int, sys.stdin.readline().split()))

    def compute_height(self):
        height = [None for _ in self.parent]
        todo = list(range(self.n))
        while 0 < len(todo):
            node = todo.pop()
            if self.parent[node] == -1:
            height[node] = 1
            elif height[node] is None:
            if height[self.parent[node]] is None:
                # We will try again after doing our parent
                todo.append(node)
                todo.append(self.parent[node])
            else:
                height[node] = height[self.parent[node]] + 1

        return max(height)


if __name__ == "__main__":
    tree = TreeHeight()
    tree.read()
    print(tree.compute_height())

(Note, I switched to a standard indent, and then made that indent 4. See this classic study for evidence that an indent in the 2-4 range is better for comprehension than an indent of 8. And, of course, the pep8 standard for Python specifies 4 spaces.)

---

Here is the same code showing how to handle accidental loops, and hardcode a specific test case.

import sys

class TreeHeight:
    def read(self):
        self.n = int(sys.stdin.readline())
        self.parent = list(map(int, sys.stdin.readline().split()))

    def compute_height(self):
        height = [None for _ in self.parent]
        todo = list(range(self.n))
        in_redo = set()
        while 0 < len(todo):
            node = todo.pop()
            if self.parent[node] == -1:
                height[node] = 1
            elif height[node] is None:
                if height[self.parent[node]] is None:
                    if node in in_redo:
                        # This must be a cycle, lie about its height.
                        height[node] = -100000
                    else:
                        in_redo.add(node)
                        # We will try again after doing our parent
                        todo.append(node)
                        todo.append(self.parent[node])
                else:
                    height[node] = height[self.parent[node]] + 1

        return max(height)


if __name__ == "__main__":
    tree = TreeHeight()
    # tree.read()
    tree.n = 5
    tree.parent = [-1, 0, 4, 0, 3]
    print(tree.compute_height())