# My Weblog

## Multiway Tree

You are given a list of edges of tree in ( parent , child ) fashion and you have to create a tree using this list. This problem is bit challenging since this tree can have any number of children.Suppose we have list [ (7 8 ) (7 9) (7 11) (7 12 ) (4 5) (5 6) (6 7) (2 3 ) (3 4) (1 2) ] so you can see root 7 has four children 8,9,11,12. Although technically i don’t know if this is multiway tree or not . Any way its good problem to practice pointers.

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;

struct tree
{
int p;
struct list  *l;
};

struct list
{
struct tree *t;
struct list *next;
};
vector<pair<int,int> > v;
map<int,int> P;
multimap<int,int> M;
void creatTree(struct tree **nd, int a , int b)
{
if((*nd)->p==a)
{

struct list *curr = (*nd)->l;
if(curr==NULL)
{
curr=(struct list *) malloc( sizeof ( struct list ) );
curr->next = NULL;
curr->t = (struct tree *) malloc ( sizeof ( struct tree ) );
curr->t->p = b;
curr->t->l = NULL;
(*nd)->l=curr;
return;
}

while(curr->next!=NULL) curr=curr->next;
curr->next = (struct list *) malloc( sizeof ( struct list ) );
curr->next->next = NULL;
curr->next->t = (struct tree *) malloc ( sizeof ( struct tree ) );
curr->next->t->p = b;
curr->next->t->l = NULL;

}
else
{
//traverse the whole list to find out suitable position for child
struct list *curr = (*nd)->l;
while(curr!=NULL)
{
creatTree( & ( curr->t ) , a , b );
curr=curr->next;
}

}
}

void print(struct tree *t,int lev)
{
cout<<"lev= "<<lev<<" node= "<<t->p<<endl;
struct list *curr=t->l;
while(curr!=NULL)
{
print(curr->t,lev+1);
curr=curr->next;
}
}

int main()
{
struct tree *root;
root=NULL;
int n,a,b;
cout<<"Enter number of edges\n";
cin>>n;
for(int i=0;i<n;i++) cin>>a>>b/*,v.push_back(make_pair(a,b))*/,P[b]=a,M.insert(pair<int,int>( a,b ));
//search for root.

int rt=-1;
for(map<int,int> :: iterator it = P.begin();it!=P.end();it++)
{
a=it->first;
b=it->second;
if(P.count(b)==0) //this is my root
{
rt=b;
break;
}
}

//linear searching over list to get the root
/*for(int i=0;i<n;i++)
{
bool flag=true;
int tmp=v[i].first;
for(int j=i+1;j<n;j++)
{
if(tmp==v[j].second)
{
flag=false;
break;
}
}
if(flag) {rt=tmp;break;}
}*/

cout<<"root is "<<rt<<endl;

if(rt==-1) cout<<"not tree.it contains cycles\n";
root=(struct tree *) malloc( sizeof ( struct tree ) );
root->p=rt;
root->l=NULL;

queue<int> Q;
Q.push(rt);
while(!Q.empty())
{
int tmp=Q.front();Q.pop();
for(multimap<int,int> :: iterator it=M.equal_range(tmp).first;it!=M.equal_range(tmp).second;it++)
{
creatTree(&root,tmp,it->second);
Q.push(it->second);
}
}
//for(int i=0;i<n;i++)  creatTree(&root,v[i].first,v[i].second);

print(root,0);

}

This is sample test case and output.
[user@localhost TCL]\$ ./a.out
Enter number of edges
10
7 8
7 9
7 11
7 12
4 5
5 6
6 7
2 3
3 4
1 2
root is 1
lev= 0 node= 1
lev= 1 node= 2
lev= 2 node= 3
lev= 3 node= 4
lev= 4 node= 5
lev= 5 node= 6
lev= 6 node= 7
lev= 7 node= 8
lev= 7 node= 9
lev= 7 node= 11
lev= 7 node= 12