Struct and Compute tree height based on an input pattern

let's say I have this input

5

4 -1 4 1 1

Explanation:
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.

0 1 2 3 4

4 -1 4 1 1

Now we can see that the node number 1 is the root because −1 corresponds to it in the second line.
Also, we know that the nodes number 3 and number 4 are children of the root node 1. Also, we know
that the nodes number 0 and number 2 are children of the node 4.

I must take this data and struct a tree. base on that input. However, I'm provided with one suggestion that I still can't fathom.

> "Suggestion: Take advantage of the fact that the labels for each tree
> node are integers in the range 0..𝑛−1: you can store each node in an
> array whose index is the label of the node. By storing the nodes in an
> array, you have 𝑂(1) access to any node given its label.
>
> allocate 𝑛𝑜𝑑𝑒𝑠[𝑛]
>
> for 𝑖 ← 0 to 𝑛 − 1:
>
> 𝑛𝑜𝑑𝑒𝑠[𝑖] =new 𝑁𝑜𝑑𝑒
>
> Then, read each parent index:
>
> for 𝑐ℎ𝑖𝑙𝑑𝑖𝑛𝑑𝑒𝑥 ← 0 to 𝑛 − 1:
>
> read 𝑝𝑎𝑟𝑒𝑛𝑡𝑖𝑛𝑑𝑒𝑥
>
> if 𝑝𝑎𝑟𝑒𝑛𝑡𝑖𝑛𝑑𝑒𝑥 == −1:
>
> 𝑟𝑜𝑜𝑡 ← 𝑐ℎ𝑖𝑙𝑑𝑖𝑛𝑑𝑒𝑥
>
> else:
>
> 𝑛𝑜𝑑𝑒𝑠[𝑝𝑎𝑟𝑒𝑛𝑡𝑖𝑛𝑑𝑒𝑥].𝑎𝑑𝑑𝐶ℎ𝑖𝑙𝑑(𝑛𝑜𝑑𝑒𝑠[𝑐ℎ𝑖𝑙𝑑𝑖𝑛𝑑𝑒𝑥])"

I tried to do the following:

set up a hashmap. the key is parents. and its children in an array list. since ill always be appending. the goal here is to compute the height of this tree.
In my hashmap, I have all the parents as the Key and all the children in the tree are the value which is represented as an ArrayList. the tree might not be binary therefore I might have a node with more than 2 children. if this implementation is a tree! why. why it's a tree and how could you name a tree since u don't have a Node class and the root is like any other parent. and if it is a tree. how do I even compute its height?

void setUpTree() {
tree = new HashMap<>(n);
int num;
for (int i = 0; i < n; i++) {
num = parent[i];
if (num == -1)
tree.put(i, new ArrayList<>());
else {
tree.computeIfAbsent(num, k -> new ArrayList<>());
tree.get(num).add(i);
}
}
}

the task itself is inscrutable to me since the tree is implemented using an Array. I implemented the setUpTree method based on what I understood
I have no idea if I'm on the right track. and if so. how to even compute the height. I'd appreciate any explanation or a hint.
thank you.

The complete starter code for Context:

public class tree_height {
static class FastScanner {
StringTokenizer tok = new StringTokenizer("");
BufferedReader in;
FastScanner() {
in = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
while (!tok.hasMoreElements())
tok = new StringTokenizer(in.readLine());
return tok.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
public static class TreeHeight {
int n;
int[] parent;
HashMap<Integer, ArrayList<Integer>> tree;
void read() throws IOException {
FastScanner in = new FastScanner();
n = in.nextInt();
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = in.nextInt();
}
}
//the implementation of the algorithm provided in the suggestion
void setUpTree() {
tree = new HashMap<>(n);
int num;
for (int i = 0; i < n; i++) {
num = parent[i];
if (num == -1)
tree.put(i, new ArrayList<>());
else {
tree.computeIfAbsent(num, k -> new ArrayList<>());
tree.get(num).add(i);
}
}
}
int computeHeight() {
//set up the tree to compute its height
setUpTree();
//Compute tree height here
}
static public void main(String[] args) throws IOException {
new Thread(null, new Runnable() {
public void run() {
try {
new tree_height().run();
} catch (IOException ignored) {
}
}
}, "1", 1 << 26).start();
}
public void run() throws IOException {
TreeHeight tree = new TreeHeight();
tree.read();
System.out.println(tree.computeHeight());
}

You can remove the setUpTree() function from computeHeight() as you are not using the tree HashMap in that function.

Let's try to calculate the time complexity

Consider the following tree:

We are calculating the depth of each node and for calculating depth of a node we are iterating till we get to the top. So for

0 we iterate over other nodes {}
1 we iterate over other nodes {0}
2 we iterate over other nodes {1,0}
3 we iterate over other nodes {2,1,0}

The overall time complexity of the algorithm is O(n^2)

Are we doing some repetitive work ?

Yes, In the third iteration we know the depth of 2, and when we are doing for 3 we can use the depth of 2. In general, we can say

    depth[node] = 1 + depth[node->parent]

Lets use this to update our algorithm

Algorithm

      a. Create an auxilary array depth where we store depth of the nodes
b. Iterate over each node:
i.  If the depth of parent of node is known then 
update depth[node]=1+depth[node -> parent] 
ii. If the depth[node->parent] is not known, then 
recursively calculate the depth and also update 
the depth of each node in the path
c. Height of the tree is the maximum depth among all the nodes

Since we are touching each node only once, the complexity of this algorithm will be O(n).

Edit

> why. why it's a tree and how could you name a tree since u don't have
> a Node class and the root is like any other parent. and if it is a
> tree.

There are various ways in which you can implement a tree data structure, similary node is a concept of tree and we can implement it in many ways . One way is to have a Node class

public class Node {
int value;
List<Node> childrens;
}

In your case we are not explicity creating a Node class, but the value of hashmap entry looks similar to this Node class. Every key in the map represent a node and its value list of its childrens. So what I want to say is that there can be multiple ways to implement a tree and yours is one of them. Your hashmap implementation is the adjacency list. In the question the tree was represented using just an array.

> how to even compute the height
> Blockquote

Height of tree can be calculated using this recursion

        heigh[node] = 1 + max( height[node->children])

Lets see how we can write it using the hashmap representation to tree you have given

Algorithm

 int  height(HashMap map, int nodeId)
if(map.get(nodeId).size() == 0)
// Its the leaf
return 0;
int maxHeightsOfSubTress = 0;
for i = 0 to map.get(nodeId).size()-1
maxHeightsOfSubTress = max(maxHeightsOfSubTress, height(map,map.get(nodeId).get(i))
return 1 + maxHeightsOfSubTress