Gopinath's solution can be extended by adding one more logic. Do in-order traversal, store it in an array or something. Keep resetting this data-structure if you hit a right leaf or a non-increasing number. Well we will need two such arrays, one for storing the current increasing sequence and other for the previous best.
*"These are my principle. If you don't like, i have others."* On Wed, Aug 11, 2010 at 1:44 PM, Divya Jain <[email protected]>wrote: > @ above > ur soln ll fail in situation like > 10 > / \ > 15 18 > / \ / \ > 22 7 17 77 > the inorder is > 22 15 7 10 17 18 77 > so the longest increasing sequence is 7-77 > but this is not a bst as 10 n 7 r nt connected > > On 24 June 2010 22:36, gopinath sikha <[email protected]> wrote: > >> We can find the solution in O(n) where n is number of nodes. >> Do an in-order traversal of the binary tree. then scan through the numbers >> and find the list and find the longest(increasing or decreasing) sequence. >> That is the size of maximum size of BST in the given binary tree. >> >> >> On Wed, Jun 23, 2010 at 11:40 AM, Raj N <[email protected]> wrote: >> >>> Find the maximum size Binary search tree in a binary tree?? >>> >>> -- >>> 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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> ---------------------------------------------------------------------- >> If u doubt your believes,u believe ur doubts >> If u fail to practise,u practises failure >> ------------------------------------------------------------ >> Thanks and Regards >> GopiNath >> >> -- >> 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]<algogeeks%[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]<algogeeks%[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.
