[algogeeks] Re: Amazon Placement Question
driver(Tree *root) { node *array = malloc(sizeof(node *) *H ); /* take the height node pointer array. this will act as source pointer of each list */ makeList(root, 0, array) } makeList(Tree *root, int level, node *array) { if(! root) return ; /*do a Depth traversal and store the list pointer*/ append(array[level], root); /*Traverse the left and right subtrees and store them in list*/ makeList(root-left, level+1, array); makeList(root-right, level+1, array); } time complexity is O(n) space complexity O(log n) ( assuming append has O(1) complexity) On Aug 1, 2:26 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: @Ram Kumar: Yes. Simple and affective. Just at each node: node-left-side=node-right node-right-side=node-side-left i.e at each node you are setting the side of each of your child. Go on and just do it for all nodes. Done. On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar harrypotter@gmail.comwrote: DONT DO A BFS!! NOT WORTH IT! CALL THE NEW POINTER AS 'SIDE' POINTER. for every root connect its left and right, for every root connect root-right and root-SIDE-left that ll do -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Placement Question
try this code guys i think there is redundancy in condition checking. if so correct me... #includestdio.h struct node { int data; struct node* left; struct node* right; struct node* sibling; }; void connectHorizontal(struct node* root) { if(root == NULL) return root; else if(root-left==NULL root-right ==NULL) return root; else { if(root-left !=NULL) connectHorizontal(root-left); if(root-right!=NULL) connectHorizontal(root-right); if(root-left!=NULL) { root-left-sibling = (root-right ? root-right : (root-sibling-left ? root-sibling-left : (root-sibling-right ? root-sibling-right : NULL))); } if(root-right!=NULL) { root-right-sibling = (root-sibling-left ? root-sibling-left : (root-sibling-right ? root-sibling-right : NULL)); } } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Placement Question
Yeah use BFS, push the nodes on a stack and make them point to each other. How they point depends on the question, which needs clarification. Should they ALL be connected to each other as in A to B and A to C and B to C or just A to B and B to C. Either way, the above approach should work fine. -Minotauraus On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 6 1 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.