thank you people. i am attending microsoft interview. Any suggestions,questions,puzles will be help full. Thank you, Siddharam
On Fri, Aug 5, 2011 at 10:24 AM, Aman Goyal <aman.goya...@gmail.com> wrote: > I know dat, but i think inorder traversal solutn is better, cos in level > order case, it wud be difficult to find the subset tht is the largest BST.. > > > @Siddharam : i think your solution is correct.. > > On Fri, Aug 5, 2011 at 10:20 AM, Dipankar Patro <dip10c...@gmail.com>wrote: > >> >> checking for BST node is quite simple. by definition, p is a node of bst >> if (p->left < p < p->right) >> each node should satisfy this condition in BST. (except for the exterior >> nodes) >> >> >> On 5 August 2011 10:13, Aman Goyal <aman.goya...@gmail.com> 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 < >>> siddharam....@gmail.com> 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 <aman.goya...@gmail.com>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 <dip10c...@gmail.com>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 <aman.goya...@gmail.com> wrote: >>>>>> >>>>>>> Yes, that can be a liable case definitely....!!! >>>>>>> >>>>>>> >>>>>>> On Fri, Aug 5, 2011 at 9:35 AM, Dipankar Patro >>>>>>> <dip10c...@gmail.com>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 <aman.goya...@gmail.com> 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 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. >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> >>>>>>>> ___________________________________________________________________________________________________________ >>>>>>>> >>>>>>>> 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 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> >>>>>> ___________________________________________________________________________________________________________ >>>>>> >>>>>> 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 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. >>>>> >>>> >>>> -- >>>> 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. >>> >> >> >> >> -- >> >> ___________________________________________________________________________________________________________ >> >> 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 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. > -- 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.
