using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        var l = new List<int> {-1, 8, 6, 0, 7, 3, 8, 9, -1, 6, 1};

        Console.WriteLine(GetTreeHeight(l));

    }

    //O(n)

    static int GetTreeHeight(List<int> nodes)

    {

        var dt = new DepthTracker(nodes);

​

        return dt.GetHeight()+1;

    }

}

​

public class DepthTracker{

    List<int> Nodes;

    int[] Depth;

    //O(n)

    public DepthTracker(List<int> nodes){

        Nodes = nodes;

        Depth = new int[Nodes.Count];

        for (var i = 0; i < Nodes.Count; i++)

        {

            if (Nodes[i] > -1 && Depth[i] == 0)

            {

                Depth[i] = CheckDepth(i); 

            }

        }

    }

    // Count number of hops from this node to the root, update depth for every node visited

    // O(1) amortized, O(n) worst case

    public int CheckDepth(int index)

    {

        if(index == -1) return 0; // never really happens

        if(Depth[index] > 0) 

            return Depth[index]; // already calculated

        var nextIdx = Nodes[index];

        if(nextIdx == -1) //this is a root node

        {

            Depth[index] = 0;

            return 0;

        }

        // might want to convert this to iterative solution + stack to prevent SOF on really large inputs, 

        // but can't be bothered right now.

        var thisDepth = CheckDepth(nextIdx) + 1; 

        Depth[index] = thisDepth;

        return thisDepth;

    }

    // O(n)

    public int GetHeight() 

    { 

        return Depth.Max();

    }

}