@Harshal: I think ur code will print the input string in a sorted order. @Snehi: Ur tree will never be balanced. and in worst case scenario there will be only right child.so in that case generation of binary tree may go upto O(n*n). P.S.: correct me if i am wrong.
On Wed, Jun 22, 2011 at 1:50 PM, Rohit Sindhu < [email protected]> wrote: > @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. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 ,08011820777 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- 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.
