Algo: 1. find height of tree
2. do level order traversal
i> at each level store the address of each tree node in the
data part of a linked node and form linked list of the nodes
ii> store the header of a linked list at a certain level in an
array
3. return array.// gives final structure
complexity - T(n) =O(n)
S(n)=O(h+n ) //h=height of tree
//CODE
//tree structure
struct node {
int data;
struct node * left, *right};
// linked list structure
struct linkNode{
struct node * data;
struct linkNode * next;
}
struct linkNode** func(struct node * root){
struct linkNode ** array;
int i, h=height(root);
for(i=1;i<=h;i++)
array[i-1]=levelOrderTraversal(root, i);
return array;// final tree structure
}
//max height of tree
int height(struct node *root){
int hL=height(root->left);
int hR=height(root->right);
return 1+ HR>HL?HR:HL;
}
struct nodelink* levelOrderTraversal(struct node*root, int level){
if(root==NULL) return NULL;
if (level==1)
return createLinkNode(root); // create a node of a singly l
struct LinkNode *ptr;
if(level>1){
ptr=levelOrderTraversal(root->left,level-1);
ptr->next=levelOrderTraversal(root->right,level-1);
}
return ptr;
}
struct linkNode * createLinkNode(struct node * root){
struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct linkNode));
newNode->data=root;
newNode->next=NULL;
}
--
Thanks & Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science & Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
