CareerCup

The number of nodes per level contributes to the density of the tree. Intuitively, density is a measure of the size of a tree (number of nodes) relative to the height of the tree.

so density can be calculated as- d=(size)/(height)

float density(struct node*root)
{
return(size(root)/height(root));
}

//calculating size
int size(struct node*root)
{
if(root==NULL) return 0;
else
return(size(root->left)+size(root->right)+1);
}
//calculating height
int height(struct node* root)
{
int l,r;
if(root==NULL) return 0;
else
{
l=height(root->left);
r=height(root->right);
if(l>r)return ++l;
else return ++r;
}
}

HI all
I think it’s a application of BFS .
Please find my algo n let me know if its fine.

1. Apply BFS on root.
2. While inserting nodes into queue give levels to all the nodes which are adjacent to the node inserted
Root ->level – 0
Root left, right child -level – 1 etc.
3. Count the nodes as there are many ways
[e.g. we can use count variable and increment whenever inserting in queue or whenever that node is coming out of the queue as each node will be inserted exactly once in the tree.]
4. maximum level no will give us height , count var will give no of nodes.
5. Calculate the density…

Complexity of algo O(N)…

int height=0,nodes=0;
Call(root,&height,&nodes);

void density(struct node *root,int *height,int *nodes)
{
        if(!root)
        {
                *height=0;
                *nodes=0;
                return;
        }
        int lh=0,rh=0,ln=0,rn=0;
        density(root->left,&lh,&ln);
        density(root->right,&rh,&rn);
        *height=max(lh,rh)+1;
        *nodes=ln+rn+1;
        return;
}

Density=nodes/height

to compute height and width together,
Assuming , Tree is made of Node.

float density(Node* t){
  if (!t)
	return Nan;  
  Queue<Node*> Q[2];
  bool qid = 0;
  Q[qid].push(t);
  uint w = 1;
  uint h = 0;
  float den = 0;
  while (!Q[qid].empty)
  {
    ++h;
    uint wt = 0;
    while(!Q[qid].empty)
       {
          Node* L = Q[qid].pop();  
          if (L -> left)
          {
            Q[!qid].push(L->left); ++wt;
          }
          if (L -> right)
          {
            Q[!qid].push(L->right); ++wt;
          }          
       }
	if (w < wt) 
		w = wt;
    qid = !qid;   
  }
  den = w / h;
  return den;
}

It was a bit difficult to write algorithm, so I wrote code, it should be quite straight forward to read it. The code has not been tested, It is more a representative of my idea of computing height and width together.

int s[100];
int leveldensity(tree *p,int level)
{
if(p!=NULL)
{s[level]++;
levedensity(p->left,level+1);
leveldensity(p->right,level+1);

}

}

Consider the following tree
A level 0 : s[0] =1
/ \
B C level 1 : s[1]=2
/ \ / \
D E F G level 2 : s[2] =4

I don't think density should be defined as ratio of no. of nodes to height. I think density should be defined as #nodes in tree / #total no. of nodes in complete binary tree of that height

WTF?

Define "density of a tree".