nice one suresh !! On Fri, Aug 5, 2011 at 10:23 AM, Dipankar Patro <[email protected]> wrote:
> if you are looking for the largest height, then the inorder approach will > work. > > @ Siddharam Suresh: you are right. The question is if the inorder is > sorted, is the only necessary condition for BST? > > > On 5 August 2011 10:19, siddharam suresh <[email protected]> wrote: > >> i didnt get *increasing inorder traversal of a tree*? >> as per my knowledge inorder traversal of BST always give sorted >> data/value. >> Thank you, >> Siddharam >> >> >> >> On Fri, Aug 5, 2011 at 10:13 AM, Aman Goyal <[email protected]>wrote: >> >>> @siddharam: nice approach, just a query.... increasing inorder traversal >>> of a tree is a sufficient condition to check for a BST ? >>> >>> >>> On Fri, Aug 5, 2011 at 10:05 AM, siddharam suresh < >>> [email protected]> wrote: >>> >>>> my idea is "go for inorder traversal find the longest sorted sequence in >>>> traversal thats the *'largest BST in a binary tree.'* " >>>> Thank you, >>>> Siddharam >>>> >>>> >>>> >>>> On Fri, Aug 5, 2011 at 10:00 AM, Aman Goyal <[email protected]>wrote: >>>> >>>>> while dequing a node from the queue, how will u check whether a bst >>>>> property is sattisfied or not ?.. >>>>> >>>>> >>>>> On Fri, Aug 5, 2011 at 9:49 AM, Dipankar Patro <[email protected]>wrote: >>>>> >>>>>> I have some upto this much currently. >>>>>> Modify the Breadth First traversal (BFT) a bit. maintain two queues, >>>>>> one is for original traversal. >>>>>> >>>>>> Start from root, BFT. when you dequeue a node, check if it satisfies >>>>>> the condition for BST. if yes add the the node to auxiliary queue, if >>>>>> not, >>>>>> leave it and add it's original children to the original queue in both >>>>>> cases. >>>>>> Some further modifications can the done to have multiple auxiliary >>>>>> queues and keep track of their heights. >>>>>> >>>>>> What say? >>>>>> >>>>>> >>>>>> On 5 August 2011 09:40, Aman Goyal <[email protected]> wrote: >>>>>> >>>>>>> Yes, that can be a liable case definitely....!!! >>>>>>> >>>>>>> >>>>>>> On Fri, Aug 5, 2011 at 9:35 AM, Dipankar Patro >>>>>>> <[email protected]>wrote: >>>>>>> >>>>>>>> The question is a bit tricky. >>>>>>>> Is it possible that the largest BST is somewhere in deeper depth, >>>>>>>> i.e. it is not necessarily consisting of the root? >>>>>>>> >>>>>>>> On 5 August 2011 08:46, Aman Goyal <[email protected]> wrote: >>>>>>>> >>>>>>>>> How to find the largest BST in a binary tree. >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> 15 >>>>>>>>> / \ >>>>>>>>> 10__________ 20 >>>>>>>>> / \ >>>>>>>>> 5 _____7____ >>>>>>>>> / \ >>>>>>>>> 2_ __5 >>>>>>>>> / \ / >>>>>>>>> 0 8 3 >>>>>>>>> >>>>>>>>> The largest BST (may or may not include all of its descendants) >>>>>>>>> from the above example should be: >>>>>>>>> >>>>>>>>> ____15____ >>>>>>>>> / \ >>>>>>>>> _10 20 >>>>>>>>> / >>>>>>>>> 5 >>>>>>>>> >>>>>>>>> >>>>>>>>> Please do not post working code, logic/algorithm or link would be >>>>>>>>> preferred. >>>>>>>>> I know it will be through recursion , still the logic part of >>>>>>>>> recursion is not clear.. would be thankful if anyone could help. >>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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. >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> >>>>>>>> ___________________________________________________________________________________________________________ >>>>>>>> >>>>>>>> Please do not print this e-mail until urgent requirement. Go Green!! >>>>>>>> Save Papers <=> Save Trees >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> >>>>>> ___________________________________________________________________________________________________________ >>>>>> >>>>>> Please do not print this e-mail until urgent requirement. Go Green!! >>>>>> Save Papers <=> Save Trees >>>>>> >>>>>> -- >>>>>> 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. >>> >> >> -- >> 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. >> > > > > -- > > ___________________________________________________________________________________________________________ > > Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > > -- > 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 SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
