it can easily be done with help of level order traversal..... 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. > -- **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 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.
