We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
So it says "Note: There are no duplicate values in the binary search tree.", meaning that the data values are not the same for any two nodes correct? Because I noticed when I changed my code to do a greater than or equal to, I passed the test. I decided to spend 5 hackoros on test case 7 and noticed there are two same data values on two of the nodes. Am I misinterpreting the problem or maybe the input? (Looking at it closer, I think they meant to put 1,2 not 2,2)
@praviteja5 you put equal sign to check for the false condition which means the problem statement holds good, i.e; if there are duplicate values it is not a binary search tree.
Am afraid, that's an inaccurate statement from the author. You can have duplicates as long as your satisfy the BST property. Just to quote Cormen, "The keys in a binary search tree are always stored in such a way as to satisfy the
binary-search-tree property:
Let x be a node in a binary search tree. If y is a node in the left subtree
of x, then y:key <= x:key. If y is a node in the right subtree of x, then
y:key >= x:key.". However the point to be noted is, the duplicate conditions are trivial.
Text in a problem description: "A binary tree is not a binary search if there are duplicate values"
Text in 'Binary Trees and Binary Search Trees' link: "Each element in the left subtree of t is less than or equal to the root element".
Which one is correct?
My question was not about < or <=. This is about duplicates allowed or not.
I didn't finish task yet. However for this part, I have couple lines:
if (n->data*<=*n->left->data) {isnotBST=true; return false;}
"<=" means no duplicates, as in problem description.
I submitted both, "<=" gives 16 points, "<" gives 11 points. So, they are not consistent.
Also: there is comment of moderator "Sorry! Java and C++ will be fixed in the next few hours". I see comment Java is working. What about C++?
There is no discrepency here. Both statements hold. In the tree there can be equivalent values. If during your search you encounter equivalent values, it IS a binary tree; however, it IS NOT a BST. That would be the difference. In the case of the equivalent values you would return 0.
Can you post your code? The fact that you're using a '>=' doesn't mean anything unless you give us the context. E.g. if you're returng FALSE when a >= check returns TRUE, that makes sense given the problem description.
Just found this comment now, I'm not sure it's good idea to post code in discussion.
Two things:
1. I pointed to discrepancy between description of problem and additional document. When I ignored info in additional document, I passed all cases.
2. See comments of numberMumbler in this discussion. I guess it's about the same.
@LinhTy i looked into your last submission and it looks like your logic is wrong. May be you could think of how to solve it. The left child of the root should be less than the root value and right child of root should be greater than the root value. If you do this, there are still some conditions to check for.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
So it says "Note: There are no duplicate values in the binary search tree.", meaning that the data values are not the same for any two nodes correct? Because I noticed when I changed my code to do a greater than or equal to, I passed the test. I decided to spend 5 hackoros on test case 7 and noticed there are two same data values on two of the nodes. Am I misinterpreting the problem or maybe the input? (Looking at it closer, I think they meant to put 1,2 not 2,2)
Same here. Passed the test cases when I put the equal to sign.
@praviteja5 you put equal sign to check for the false condition which means the problem statement holds good, i.e; if there are duplicate values it is not a binary search tree.
Am afraid, that's an inaccurate statement from the author. You can have duplicates as long as your satisfy the BST property. Just to quote Cormen, "The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y:key <= x:key. If y is a node in the right subtree of x, then y:key >= x:key.". However the point to be noted is, the duplicate conditions are trivial.
hmmm. I had the opposite experience with test case 7: I had to remove the equal signs in the comparison and just check greater/less than
of course, I ended up implementing using a stack instead of using recursion, so my logic is a bit different
Text in a problem description: "A binary tree is not a binary search if there are duplicate values" Text in 'Binary Trees and Binary Search Trees' link: "Each element in the left subtree of t is less than or equal to the root element". Which one is correct?
Either is valid as long as the problem creator is consistent and the test cases match the chosen definition.
My question was not about < or <=. This is about duplicates allowed or not. I didn't finish task yet. However for this part, I have couple lines: if (n->data*<=*n->left->data) {isnotBST=true; return false;} "<=" means no duplicates, as in problem description. I submitted both, "<=" gives 16 points, "<" gives 11 points. So, they are not consistent. Also: there is comment of moderator "Sorry! Java and C++ will be fixed in the next few hours". I see comment Java is working. What about C++?
With death comes honor, with honor, redemption.
There is no discrepency here. Both statements hold. In the tree there can be equivalent values. If during your search you encounter equivalent values, it IS a binary tree; however, it IS NOT a BST. That would be the difference. In the case of the equivalent values you would return 0.
Can you post your code? The fact that you're using a '>=' doesn't mean anything unless you give us the context. E.g. if you're returng FALSE when a >= check returns TRUE, that makes sense given the problem description.
Just found this comment now, I'm not sure it's good idea to post code in discussion. Two things: 1. I pointed to discrepancy between description of problem and additional document. When I ignored info in additional document, I passed all cases. 2. See comments of numberMumbler in this discussion. I guess it's about the same.
@LinhTy i looked into your last submission and it looks like your logic is wrong. May be you could think of how to solve it. The left child of the root should be less than the root value and right child of root should be greater than the root value. If you do this, there are still some conditions to check for.
How did you manage to interpret the testcase input? All I got was just a bunch of numbers.