Finding the tree height in Python
You don't need to explicitly build the tree to compute its depth.

class TreeDepth(object):
    def __init__(self, parents):
        self._parents = parents
        self._n = len(parents)
        self._max_depth = None
        self._depths = [None] * self._n

    def max_depth(self):
        if self._max_depth is None:
            for idx, parent in enumerate(self._parents):
                depth = self.get_depth(idx)
                if self._max_depth &lt; depth:
                    self._max_depth = depth
        return self._max_depth

    def get_depth(self, idx):
        depth = self._depths[idx]
        if depth is not None:
            return depth
        parent = self._parents[idx]
        if parent == -1:
            depth = 1
        else:
            depth = self.get_depth(parent) + 1
        self._depths[idx] = depth
        return depth

&gt;&gt;&gt; TreeDepth([4, -1, 4, 1, 1]).max_depth()
3


If my math is good, this goes over each item in self._parents at most twice, so it will have \$O(n)\$ performance. Also, I have used a recursive approach to compute the depth, but if speed is your main goal, you will probably want to turn that into an iterative approach:

def max_depth2(self):
    if self._max_depth is not None:
        return self._max_depth
    for idx, parent in enumerate(self._parents):
        parent_stack = []
        while parent != -1 and self._depths[idx] is None:
            parent_stack.append(idx)
            idx, parent = parent, self._parents[parent]
        if parent == -1:
            depth = 1
        else:
            depth = self._depths[idx]
        while parent_stack:
          self._depths[parent_stack.pop()] = depth
          depth += 1
        if self._max_depth &lt; depth:
            self._max_depth = depth
    return self._max_depth