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 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@ iiita.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@ iiita.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.
?? -- 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.
> @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.
@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.
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 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 > 1>The first element in Pre-order traversal is root of tree. > 2>find its index in the inorder traversal ( I ) . > 3>All 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. > 4>Perform 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.
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 1>The first element in Pre-order traversal is root of tree. 2>find its index in the inorder traversal ( I ) . 3>All 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. 4>Perform 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.
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 wrote: > 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.
[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.
[algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.
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.
