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
Level Order traversal if you are ok with the Nulls being stored.
Otherwise its pre order traversal.
On Aug 30, 12:34 pm, Vidit Sinha vidit.it...@gmail.com wrote:
whats the final answer guys? Level order traversal??
On Tue, Aug 30, 2011 at 12:56 AM, Don dondod...@gmail.com wrote:
I'm
Because the original poster specified that space efficiency is
important, I would go with pre-order. There are typically as many
nulls in a tree as there are nodes, so you could double the size of
the file by including nulls.
Don
On Aug 30, 8:15 am, Dumanshu duman...@gmail.com wrote:
Level Order
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
@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
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
@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
@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
@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
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 )
@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,
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
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
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
@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
@Dhriti,
can you explain your point with any example? Two traversals(inorder
compulsory) are required to uniquely construct a tree. It's not that
you just want to create any BST with same nodes. Original tree needs
to be constructed. Let me know if you disagree.
On Aug 28, 6:03 pm, Dhriti Khanna
@ 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
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
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
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:
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
@Dhriti
how about this one
6
4 7
3 5 8
1112
your preorder is
6 4 3 5 7 8 11 12
try reconstruction
@ 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
23 matches
Mail list logo
