cant understand whats wrong
ques:https://hack.codingblocks.com/app/contests/1289/340/problem
code:https://ide.codingblocks.com/s/239345
Count BST subtrees that lie in given range
@bhaskar0_0
I think there is some issue with the question
BST can’t be constructed from inorder traversal alone
This might be preorder traversal
Your tree is not probably correct
Your logic for count is fine
So make tree assuming input is preorder
1 Like
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.
@Aarnav-Jindal-1059677350830863
the tree is getting constructed just fine.The traversal shows the right output.is there a fault in the logic as the output for the test case is wrong but for other cases it is working fine.Eg for case 10 20 30 40 the ans it is giving is 4 but for 10 20 30 40 50 it is giving 0(low=1 and high=45).Can’t understand this!!!
bro there can be so many bst possible with same inorder traversal.
to construct a unique bst we need some more information apart from the inorder traversal , which is missing in this question.
try building balanced bst , may be that will work .
1 Like
Bro I understand what you saying but in the question isn’t the sample output wrong as the ans given is 3 but it should be 0 as there is no node where all the nodes below it lie in the given range.It is a right skewed tree and the last node is not in the range so and should be 0?
we cannot say that the given tree is a right skewed just by looking at its inorder traversal.
some additional information is needed to uniquely determine the structure of the tree which is missing in the problem.
1 Like