Re: [algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
+1 Akshat On 7/7/12, Akshat Sapra sapraaks...@gmail.com wrote: There is no need to use any other data structure or sort the array one can directly construct the BST from a given array by taking one element at a time from the beginning and inserting into a BST. -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- 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: Write a C program to reconstruct a BST from a given array of preorder traversal.
There is no need to use any other data structure or sort the array one can directly construct the BST from a given array by taking one element at a time from the beginning and inserting into a BST. -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- 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.
[algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
@Navin : Why r u sorting the array .. BST can be made using the preorder traversal if null nodes are well defined in the given traversal.. Right?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VCvNv0yZtxMJ. 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.
[algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HQ_TvoKSLNgJ. 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.
[algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
Vindhya - Navin is right because in case of BST, if you sort the preorder array you will get inorder array. This means you already have information about the inorder, if you given preorder/postorder/levelorder. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/RxgCU_O2m9kJ. 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: Write a C program to reconstruct a BST from a given array of preorder traversal.
^ Thank you! Mind discussing the algorithm please? On Wed, Jul 4, 2012 at 7:06 PM, deepikaanand swinyanand...@gmail.comwrote: code :- http://ideone.com/O5yuo -- 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: Write a C program to reconstruct a BST from a given array of preorder traversal.
thanks all On Wed, Jul 4, 2012 at 10:57 PM, Navin Gupta navin.nit...@gmail.com wrote: Given a pre-order traversal, we can sort it to get the inorde traversal. Sorting the preorder is O( NLogN ). Now as we know the ordering of elements is Preorder - Root - Left Child - Right Child Inorder - Left Child - Root - Right Child 1The first element in Pre-order traversal is root of tree. 2find its index in the inorder traversal ( I ) . 3All the elements to the left of root in inorder traversal consist Left-Subtree ( IL ) of the root while those to the right consist Right-Subtree ( IR ) of the root. 4Perform the steps 1-3 recursively for the IL IR. Searching is LogN, so constructing the entire tree is O(NLogN). Even though we can use hash to get O(1) search complexity. But still sorting the preorder to get inorder is O ( NLogN ). -- Navin Kumar Gupta Final Year,B.Tech(Hons.) Computer Science Engg. National Institute of Technology,Jamshedpur Mobile - (+91)8285303045 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wmkx-kDe3EEJ. 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. -- Vindhya Chhabra -- 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.
[algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
@Navin
I dont think der is any need to sort the preorder traversal
given ...it will cost u more
as sorting take O(n log n ) and recursion alone will take O(n^2)
{mentioned in step 4 }
sO the overall complexity will be the sum of two..+ space of O(n) //to
store inorder traversal
--
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.
