Find height of tree - being an interviewer

FindHeightOfTree.cpp

//Problem statement:
// A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. 
// The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes
// that node with id k is the root. For ex:

//
//5    3   3       4      -1         2
//0    1   2       3       4         5
// In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4. 


// Given such an array, find the height of the tree.

//Analysis by the interviewee:
//    3           
//  0 1 2        
         \
//        4       
//           

//if(hasChildren)
//n++
//call function on all children
//if not 
//return(n)

// Discussion between two of us after coding:
//    3          0
//  0 1 2        1
         \
//        4      2
//           
//
//5    3   3       4      -1         2
//0    1   2       3       4         5

//  1+l[5]  1+l[3]  1+l[4]   0        1+l[2]  
    
//  2 2 2 1  3    Level array  

// Here is the code I reviewed and convinced in the mock interview the time complexity is O(n), n is nodes in the tree. It is 
// optimal. 

#include <iostream>
#include <vector> 
//return max height
//id is the node we are currently on

//3 3 3 -1 2 


//O(n)

//T(n) = T(c1) + T(c2) + T(c3) + ... T(cn)
// argument: you will visit the same more than once in your depth first search
// you do not do memorization
// if you have level array, and also you look up the array - height
// then you can possible to get O(n), n is size of the array
// mechanism
//    3
      |       0
//  0 1 2        1
      |  \
//    5   4      2

//-> 0 1 2 3 4  -> what is time to build this array O(n)
//       4 0
//         1
//         2
int maxHeightDfs(std::vector<std::vector<int>> c, int h,int id){
  if(c[id].size() == 0){
    return(h);
  }
  else{
    h++;
    int max = 0;
    int height;
    for(int i = 0; i < c[id].size(); i++){  // O(n), n array size
      height = maxHeightDfs(c,h,c[id][i]); // height of tree
      
      if(height > max){
        max = height;
      }
    }
    return(max);
  }
}

int findHeight(std::vector<int> nodes){
  std::vector<std::vector<int>> children (nodes.size());
  
  //find root
  int root;
  for(int i = 0; i < nodes.size(); i++){
    if(nodes[i] == -1){
      root = i;
    }
  }
  
  
  //O(n)
  for(int i = 0; i < nodes.size(); i++){
    if(nodes[i] == -1){
      continue;
    }
    children[nodes[i]].push_back(i);
  }
  //children[i] would return an array of all children of node with id i
  
  // for(int i = 0; i < children.size(); i++){
  //   for(int j = 0; j < children[i].size(); j++){
  //     std::cout << i << " has child " << children[i][j] << std::endl;
  //   }
  // }
  
  return(maxHeightDfs(children,0,root));
}

int main() {
  
  //
  
  std::vector<int> nodes = {3,3,3,-1,2,4};
  
  std::cout << "Height: " << findHeight(nodes) << std::endl;
  return 0;
}




//