Dude, yeah I got the algo, but can u write java code for that On Fri, Jul 30, 2010 at 6:03 PM, karthik ramanathan <[email protected] > wrote:
> 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, vineel. -- 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.
