2

I came upon this question on a "Practice Final" that I am using to study for the real final:

enter image description here

I can't think of why this method wouldn't work. The logic seems fine. A BST is only a BST if each left < parent < right, which is precisely what this method checks, recursively.

Any hints would be appreciated!

MathMajor
  • 269
  • 1
  • 2
  • 13
  • perhaps the `false` branches should also check for equality – M.M Dec 07 '14 at 07:01
  • Okay, I don't think that's it though. I believe a BST where left <= parent <= right would still have all the properties of a regular BST. – MathMajor Dec 07 '14 at 07:07
  • Suppose you have a BST like this: `{0} | {-2, 2} | {, 1}, {-1, }`. Then `root->left->right > root` but passes your test. – Iwillnotexist Idonotexist Dec 07 '14 at 07:09
  • The only property of BST is that left < parent < right. I don't think it says every left node of every left sub tree must be < root. – MathMajor Dec 07 '14 at 07:15
  • 1
    @GabrielH: Yes it does. That's the whole point of a BST. When searching for a value, you just compare it with the current node and then follow either the left or the right subtree. This requires **all** nodes on the left (right) to be not greater (lesser) than the current node. – NPE Dec 07 '14 at 07:17
  • False. It does say that, but that's not the property at issue. The property at issue is that all elements of the right subtree of the left child of a node are < than said node in a BST. – Iwillnotexist Idonotexist Dec 07 '14 at 07:17
  • 1
    Okay - It turns out that I didn't know what a BST was all this time. It's amazing I made it this far :). – MathMajor Dec 07 '14 at 07:28

1 Answers1

3

Duplicate values aside, the definition of a binary search tree requires that:

The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.

The code in your question does not check that. Consider the following tree:

  2
 /
1
 \
  3

This would pass the test, but isn't a valid BST: for this to be a BST, 3 has to be be in the right subtree of 2.

See https://stackoverflow.com/a/759851/367273 for an example of a correct implementation.

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012