Prove that this assumption doesn't work for all binary search trees

Question

(Binary search tree is a binary tree where each node can have 2 children atmost, the right being larger than the node, and the left should be smaller than the node.)

I have a theory that i want to disprove. It says that for any binary tree, the if we take a search path (call it S) to a leaf node, then any node on the LEFT of S must be smaller than any node on S, and any node of the RIGHT must be larger than any node on S. In other words: node on left < node on S < node on right. Is there any counter-example to disprove this theory?

For example if we have this tree:

A search path for node K would be M->F->H->K

The set of nodes on the left contains C, A, D, G

The set on the right contains V,S,P,T,X,W

What is a good counter example?

Thank you.

You have a strange definition of "right" and "left".. Surely C, A, D, G are to the left of M->F-H->K? — Blorgbeard
Any node on the left side of M->F-H->K (the search path) belongs to the "left" set. Anything on the right belongs to the "right" set. — Osama Aref
So "The set of nodes on the right contains C, A, D, G" is incorrect, yes? — Blorgbeard
Anyway, counter-example: M->F->C->A. The D node is the right of the line, but is not larger than M or F. — Blorgbeard

twalberg twalberg · Accepted Answer · 2016-12-05T21:24:45

This isn't really an answer, but it wouldn't fit in a comment...

I think your definition of "binary search tree" is a bit lacking - after all, this would meet your definition:

   B
    \
     C
    / \
   A   D

However, that's not a true binary search tree - your definition lacks the recursive relationship. In a binary search tree, all elements in the left subtree of a node are less than the node label, and all elements in the right subtree are greater - not just the immediate children.

Perhaps having a more precise definition would help you in thinking about your "theory".

Prove that this assumption doesn't work for all binary search trees

1 Answers