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.
