Compute Tree Height-Data Structure-Coursera Course

Compute Tree Height-Data Structure-Coursera

#include <bits/stdc++.h>
using namespace std;
int root=0;
int main()
{
  int n;
  cin>>n;
  vector< vector<int> >nodes(n);
  queue<int>q;
  int a[n];
  for(int i=0;i<n;i++)
  {
	  cin>>a[i];
	  if(a[i]==-1)root=i;
	  else {
		  nodes[a[i]].push_back(i);
	  }
  }
  q.push(root);
  int height=0;
  while(true)
  {
	  int nodecount=q.size();
	  if(nodecount==0){
		  cout<<height<<endl;
		  return 0;
	  }
	  height+=1;
	  while(nodecount>0){
		  int node=q.front();
		  q.pop();
		  if(!nodes[node].empty()){
			  for(int i=0;i<nodes[node].size();i++)
				  q.push(nodes[node][i]);
		  }
		  nodecount--;
	  }
  }
    return 0;
}

I have gone through your solution, but I can't understand how they are making tree . I know -1 becomes the root, but what about other nodes? Please explain the question, I have read this on internet, but this whole question seems incomplete to me. How we put other nodes in tree except the root.

Thank You in advance.

Thanks I got the whole question and algo.

@Ujjk29 is it possible that you can share what you learned? I am a little confused about how they complete the order of the nodes too. thanks

thank you. im going to solve this problem by recursion and using struct too.

Very nicely written code.

Thanks I got the whole question and algo.

Can you share your knowledge?

Can you please explain the method you have applied to get the height of tree?