My code is passing 3/4 test cases and I am unable to figure out where is it going wrong. Kindly help. Here’s my code :
Largest BST in a BInary tree
hi @Puneet_Sharma
you approach is wrong you are only checking with immediate neighbors but you also need to check that present node is greater than the max of left subtree also present node is less of equal to min of right subree.
Check if tree with current node as root is a valid BST and if it is then return its size.
If tree with current node as its root is not a valid BST, then make recursive calls to left and right sub-trees and return the maximum of values returned by these recursive calls. Condition for valid BST could be checked by creating inorder array and checking if it is sorted.
The worst case time complexity of above algorithm is O(n^2) which occurs when the binary tree is skewed one with each node having only right child which is less than its parent.
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.