Please check it ASAP
Only samlpe test case passing for largest BST in a BT
@TheAlgo hey dhiraj your code is not working
9
50 30 5 20 60 45 70 65 80
5 30 20 50 45 60 65 70 80
your output is
3
but expected output is
5
and your code is also not working
for this case
7
20 8 4 12 10 14 22
4 8 10 12 14 20 22
your output is 4
but output is 7
so try to handle these senario if you will not able to handles these cases then we will discuss a simpler approach.
yeah thats what i am asking why is my code not working what is the concept which is going wrong for me
Can you get me a single approach?
@TheAlgo The simplest is to traverse the binary tree in preorder fashion and for each encountered node ,we check whether the subtree root at the node is bst or not.If the subtree is a Bst ,we calculate and return the size of the subtree rooted at the node.otherwise ,we return the maximum size Bst returned by the left and right subtree.
how to write code for this problem is that
1 Make a size function which calculate the size of a given binary tree which recursively will calculate the size of the left subtree and right subtree +1
2 make a isBst Recursive function which determine if given Binary tree is a Bst on by keeping a valid range (starting from [MIN_VALUE,MAX_VALUE]
keep shrinking it down for each node as we go down recursivrely
3 make a findLargestBst which is a helper function which send root to isBst function .
Can you see my code once I guess I have used the same approach
@TheAlgo hey Dhiraj I made some modification in your code
now it working fine.
for better understanding do a dry run on it.
Was I not doing it for the right left subtree and instead doing it only with the main root
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
complexity is O(N^2) ?