CODEWITHSUNDEEP
recursionbinary-treebinary-search-tree
MathMajor
MathMajor

Reputation: 279

What is wrong with this method that checks if a tree is a BST or not

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!

Upvotes: 2

Views: 107

Answers (1)

NPE
NPE

Reputation: 500903

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.

Upvotes: 3

Related Questions