Bad Tree design, Data Structure

Question

I tried making a Tree as a part of my Data Structures course. The code works but is extremely slow, almost double the time that is accepted for the course. I do not have experience with Data Structures and Algorithms but I need to optimize the program. If anyone has any tips, advices, criticism I would greatly appreciate it.

The tree is not necessarily a binary tree.

Here is the code:

import sys
import threading

class Node:
    def __init__(self,value):
        self.value = value
        self.children = []
        self.parent = None
    def add_child(self,child):
        child.parent = self
        self.children.append(child)

def compute_height(n, parents):
    found = False
    indices = []
    for i in range(n):
        indices.append(i)
    for i in range(len(parents)):
        currentItem = parents[i]
        if currentItem == -1:
            root = Node(parents[i])
            startingIndex = i
            found = True
            break
    if found == False:
        root = Node(parents[0])
        startingIndex = 0
    return recursion(startingIndex,root,indices,parents)


def recursion(index,toWhomAdd,indexes,values):
    children = []
    for i in range(len(values)):
        if index == values[i]:
            children.append(indexes[i])
            newNode = Node(indexes[i])
            toWhomAdd.add_child(newNode)

            recursion(i, newNode, indexes, values)
        


    return toWhomAdd


def checkHeight(node):
    if node == '' or node == None or node == []:
        return 0
    counter = []
    for i in node.children:
        counter.append(checkHeight(i))
    if node.children != []:
        mostChildren = max(counter)
    else:
        mostChildren = 0
    return(1 + mostChildren)

def main():
    n = int(int(input()))
    parents = list(map(int, input().split()))
    
    root = compute_height(n, parents)
    print(checkHeight(root))
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()

Edit:

For this input(first number being number of nodes and other numbers the node's values)

5
4 -1 4 1 1

We expect this output(height of the tree)

3

Another example:

Input:

5
-1 0 4 0 3

Output:

4

Answer 1

It looks like the value that is given for a node, is a reference by index of another node (its parent). This is nowhere stated in the question, but if that assumption is right, you don't really need to create the tree with Node instances. Just read the input into a list (which you already do), and you actually have the tree encoded in it.

So for example, the list [4, -1, 4, 1, 1] represents this tree, where the labels are the indices in this list:

                      1
                     / \
                    4   3
                   / \
                  0   2

The height of this tree — according to the definition given in Wikipedia — would be 2. But apparently the expected result is 3, which is the number of nodes (not edges) on the longest path from the root to a leaf, or — otherwise put — the number of levels in the tree.

The idea to use recursion is correct, but you can do it bottom up (starting at any node), getting the result of the parent recursively, and adding one to 1. Use the principle of dynamic programming by storing the result for each node in a separate list, which I called levels:

def get_num_levels(parents):
    levels = [0] * len(parents)

    def recur(node):
        if levels[node] == 0:  # this node's level hasn't been determined yet
            parent = parents[node]
            levels[node] = 1 if parent == -1 else recur(parent) + 1
        return levels[node]

    for node in range(len(parents)):
        recur(node)

    return max(levels)

And the main code could be as you had it:

def main():
    n = int(int(input()))
    parents = list(map(int, input().split()))
    
    print(get_num_levels(parents))