1 tc is failed..whats the error?

#1
#2

@garganshul151 your BST check is incorrect!
try this test
7
5 4 1 6 6 3 8
1 4 6 5 3 6 8
here largest BST is of size 3 but your output is 7.

#3

so what should be the correction?

#4

@garganshul151 maintain a value ranges low, high and pass towards left->(low,root->val) and to right->(root->val,high)
BST is validated only when every node value satisfies-> low< root->val<=high.

#5

https://ide.codingblocks.com/s/315780…i have updated some plz see whats the error now

#6

someone answer please…i want the code for the correction

#7

@garganshul151 checkBST should be a boolean function, which returns true if root is BST else false, now if given root is BST find number of nodes under this root and that’s your answer, otherwise if this root is not BST, check for root->left and root->right.
Overall complexity is O(n^2) which can be reduced to O(n),(actually this is what interviewer expects). For further clarification, I recommend you watch this


try implementing this, then I will provide you my code if you are unable to do it in O(n).
#8

i am not able to get how to modify that in my code…plz tell the necessary correction in my code only.

#9

@garganshul151 here you go