Re: [algogeeks] Re: How to save a binary search tree space efficiently
whats the final answer guys? Level order traversal?? On Tue, Aug 30, 2011 at 12:56 AM, Don dondod...@gmail.com wrote: I'm not sure if this is what you are looking for, but I once came up with a way to save a binary tree in such a way that when it is rebuilt, it will be balanced. You don't get back the exact same tree with all the nodes in the same position, but you do get the same nodes in a balanced configuration. Start by doing an inorder traversal and storing each node sequentially in an array. Then call a recursive function called saveTree(first, last), where first and last are the first and last indices of the array. saveTree does the following if: write middle item of array to the file call saveTree on left half of array call saveTree on right half of array When you rebuild the tree adding the nodes in the order in which they occur in the file, the resulting tree will be balanced. Don On Aug 28, 1:29 am, rohit rajuljain...@gmail.com wrote: How to save a binary search tree space efficiently and built it again , just tell any idea. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
level order traversal can be a solution but since it is BST that we want to store not binary tree(we can store binary tree using level order trav and can reconstruct tree out of it) so we can just store the preorder traversal, at time of reconstructing,scan through this traversal and pass the parent node to child to determine position of child wrt parentdo this for all n nodes -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@vikas : you can use recursive approach to draw tree here we go: 6 4 3 5 7 8 11 12 1 ) 6 is root since 4 6 , 4 is left child of 6 2) find value which is more than 6 , so it is 7 in this case... hence 7 is right child. 3 ) Hence we break this list in three part; 1. Root node (6)2. left sub tree (4,3,5) 3. right subtree (7,8,11,12) 6 / \ (4,3,5) (7,8,11,12) we repeat same 3 steps for left and right sub tree. So we need only one Preorder traversal. On Mon, Aug 29, 2011 at 1:22 AM, vikas vikas.rastogi2...@gmail.com wrote: @ Sagar, level order can be stored but you need to remember the nulls always On Aug 29, 12:06 am, sagar pareek sagarpar...@gmail.com wrote: level order traversal is best for this case :) On Sun, Aug 28, 2011 at 11:53 PM, prashant thorat prashantnit...@gmail.comwrote: only preorder will suffice.. considering fact that it's BST On Sun, Aug 28, 2011 at 11:26 PM, Rishabbh A Dua duarish...@gmail.com wrote: Please correct me if i am wrong but isnt the answer to this q is AVL trees On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.com wrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Rishabbh A Dua -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
store inorder traversal in the array and while reconstructing form a tree around mid element using recursion... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@ankit: I think it wont work in below case : 9 \ 18 \ 27 \ 36 Inorder traversal : 9-18-27-36 mid element is 18 or 27 On Mon, Aug 29, 2011 at 12:59 PM, ankit gupta ankit.itc...@gmail.comwrote: store inorder traversal in the array and while reconstructing form a tree around mid element using recursion... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@prashant it is the same mid value as u calculate in binary search i.e. (lowest index+highest index)/2 No matter whether it is 18 or 27,u gonna get almost balanced BST every time if u do construct the tree as ankit has mentioned. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@prateek but you wont get same tree back always .. you get only balanced tree take a look below: 9 9 \ \ 18 10 / \ \ 10 27 18 \ 27 Both are BST but this case inorder traversal wont get back original tree On Mon, Aug 29, 2011 at 3:09 PM, PRATEEK VERMA prateek...@gmail.com wrote: @prashant it is the same mid value as u calculate in binary search i.e. (lowest index+highest index)/2 No matter whether it is 18 or 27,u gonna get almost balanced BST every time if u do construct the tree as ankit has mentioned. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@vikas: in case of BT u can save it using BFS and construct it back .. On Mon, Aug 29, 2011 at 8:42 PM, vikas vikas.rastogi2...@gmail.com wrote: yep, I realized the mistake. thanks for the clarification. BTW, what approach will be suitable in Bin Tree, extensible to MST . On Aug 29, 11:49 am, prashant thorat prashantnit...@gmail.com wrote: @vikas : you can use recursive approach to draw tree here we go: 6 4 3 5 7 8 11 12 1 ) 6 is root since 4 6 , 4 is left child of 6 2) find value which is more than 6 , so it is 7 in this case... hence 7 is right child. 3 ) Hence we break this list in three part; 1. Root node (6)2. left sub tree (4,3,5) 3. right subtree (7,8,11,12) 6 / \ (4,3,5) (7,8,11,12) we repeat same 3 steps for left and right sub tree. So we need only one Preorder traversal. On Mon, Aug 29, 2011 at 1:22 AM, vikas vikas.rastogi2...@gmail.com wrote: @ Sagar, level order can be stored but you need to remember the nulls always On Aug 29, 12:06 am, sagar pareek sagarpar...@gmail.com wrote: level order traversal is best for this case :) On Sun, Aug 28, 2011 at 11:53 PM, prashant thorat prashantnit...@gmail.comwrote: only preorder will suffice.. considering fact that it's BST On Sun, Aug 28, 2011 at 11:26 PM, Rishabbh A Dua duarish...@gmail.com wrote: Please correct me if i am wrong but isnt the answer to this q is AVL trees On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.com wrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Rishabbh A Dua -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
Does ur tree has parent pointer ? Sanju :) On Sun, Aug 28, 2011 at 1:09 AM, Navneet navneetn...@gmail.com wrote: Store any two traversals (inorder must) and reconstruct it later. Total space 2n (n = number of nodes) On Aug 28, 11:29 am, rohit rajuljain...@gmail.com wrote: How to save a binary search tree space efficiently and built it again , just tell any idea. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@Navneet: I think only saving the preorder traversal will do. O(n). Inserting back into that order will give me the original tree back.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
@ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
we can use m-way search tree to save some space. And reconstruction is pretty simple as all of us know. any suggestions? On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.comwrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- *MOHIT VERMA* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
Please correct me if i am wrong but isnt the answer to this q is AVL trees On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.comwrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Rishabbh A Dua -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
only preorder will suffice.. considering fact that it's BST On Sun, Aug 28, 2011 at 11:26 PM, Rishabbh A Dua duarish...@gmail.comwrote: Please correct me if i am wrong but isnt the answer to this q is AVL trees On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.comwrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Rishabbh A Dua -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: How to save a binary search tree space efficiently
level order traversal is best for this case :) On Sun, Aug 28, 2011 at 11:53 PM, prashant thorat prashantnit...@gmail.comwrote: only preorder will suffice.. considering fact that it's BST On Sun, Aug 28, 2011 at 11:26 PM, Rishabbh A Dua duarish...@gmail.comwrote: Please correct me if i am wrong but isnt the answer to this q is AVL trees On Sun, Aug 28, 2011 at 10:43 PM, Dhriti Khanna dhriti0...@gmail.comwrote: @ Navneet: See if the tree is: 6 4 7 3 5 8 Then the preorder traversal is : 6 4 3 5 7 8 And using this preorder traversal and inserting them in the tree one by one, we generate this exact tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Rishabbh A Dua -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Yours affectionately, Prashant Thorat Computer Science and Engg. Dept, NIT Durgapur. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.
