@snehi .. your solution does not come upto the O(n) as for n elements of string it will take O(lg n) for each , so a total of O ( n * lg n )
Otherwise a better variation to Solution is taking a count member in each node and incrementing it when another occurrence is made of that character. Correct me if i am wrong , On Thu, Jun 23, 2011 at 12:51 AM, snehi jain <[email protected]> wrote: > the binary tree for the above example will be > k(1) > \ > a(2) > / \ > (7) a p(3) > \ > i(4) > \ > l(5) > \ > r (6) > > number in the bracket denotes the order of insertion like k inserted first > then a then p > and so on .. > now if inorder is performed ... arent we getting " kaapilr " > > On Thu, Jun 23, 2011 at 12:43 AM, oppilas . <[email protected]>wrote: > >> May be I didn't understood your logic. >> According to original question for >> I/P ----kapilra >> O/P --kaapilr.. >> Now, >> -what if we create a binary tree with root as the first element of the >> string and if the next character is equal then place it to left else place >> it to right. Similar comparison will be done while inserting all the other >> nodes too . >> >> At root you will insert k(count=1) >> After that a >> >> k(1) >> / >> a(1) >> Then you will insert p, >> k(1) >> / \ >> a(1) p(1) >> And so on. >> >>> >>>> after that if InOrder traversal is performed.. it would give us the >>>> desired output. >>>> >>> >> If by inoder traversal we can get desired output then please how me how >> using a small example :). >> >> >>> >>>> Snehi >>>> >>>> >>>> On Wed, Jun 22, 2011 at 9:48 PM, DK <[email protected]> wrote: >>>> >>>>> No. This is equivalent to a sort with comparisons based on index of >>>>> first occurrence in the input string. Any comparative algorithm is O(n log >>>>> n) and a non comparative algorithm can be O(n) only by using counting or >>>>> radix sorting etc. >>>>> >>>>> -- >>>>> DK >>>>> >>>>> http://twitter.com/divyekapoor >>>>> http://www.divye.in >>>>> >>>>> -- >>>>> 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/-/GeqwF_snzQQJ. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > Regards , -- Rohit Sindhu -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
