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.
@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.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
@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.