Do a BFS, by having a queue and keep inserting the nodes into it. You should know how many nodes are there in each level, for which you can have a variable to count the number of nodes in each level. The when you remove from your queue do connect these nodes till your count. You may need to use one more temp variable to not to lose the previous level node count when you compute the next level node count. Repeat the same for all the level.
RK On Fri, Jul 30, 2010 at 11:21 AM, Amit Agarwal <[email protected]> wrote: > A simple queue implementation will do. > > -Regards > Amit Agarwal > blog.amitagrwal.com > > > > > On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee > <[email protected]>wrote: > >> >> >> On 30 July 2010 02:59, Priyanka Chatterjee <[email protected]> wrote: >> >>> 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){ >>> struct nodeLink * ptr1, *ptr2; >>> ptr1=levelOrderTraversal(root->left,level-1); >>> ptr2=levelOrderTraversal(root->right,level-1); >>> >> >> if(ptr1==NULL && ptr2==NULL) return NULL; >> if(ptr1==NULL) return ptr2; >> if(ptr2==NULL) return ptr1; >> ptr1->next=ptr2; >> >> return ptr2; >> >>> } >>> >>> } >>> >>> >> >>> 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/ >>> >> >> >> >> -- >> 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]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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.
