3
$\begingroup$

Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ or it is less than or equal than the key of the right child.

To prove that if $T$ is BST then for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child I could say that from the definition of BST it follows that given a node $x$ and a node $y$ which belongs to the left sub-tree of $x$ then $key(y) \le key(x)$.

By the hypothesis if we choose any node $z$ of in the left sub-tree of $y$ then $key(z) \le key(y)$ so the relation holds true for all of the nodes of the tree.

I'm not sure how to approach the proof of the second direction: if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child then $T$ is a BST.

Improve this question
$\endgroup$
3
  • $\begingroup$ In your proposition: "if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ OR it is less than or equal than the key of the right child", shouldn't OR be replaced with AND. Even in that case you will already have a definition of a BST, so no need to prove it. $\endgroup$
    – fade2black
    Commented Jun 16, 2017 at 9:03
  • $\begingroup$ @fade2black the key of $x$ can be larger OR equal than the key of its left child $y$ why does it have to be AND? Also you're saying no need for further proof in the first direction but what about the second direction? $\endgroup$
    – Yos
    Commented Jun 16, 2017 at 9:06
  • $\begingroup$ you write: "...the key of $x$ is larger or equal than the key of the left child of $x$ OR it is less than or equal than the key of the right child". Pay attention to the second 'or' (uppercase 'or). Consider a three node @Yos, binary tree (1)<--left--((3)) --right-->(2), 3 is root, 1 is the left child and 2 is the right child. So your proposition is TRUE: (node 3 is a non-leaf) and ( (3 is larger than or equal to the left child 1) OR (3 is less than or equal to 2 ) . But the tree is not a BST. $\endgroup$
    – fade2black
    Commented Jun 16, 2017 at 9:19

1 Answer 1

Reset to default
3
$\begingroup$

The second direction is not always true, in a BST all elements in the right subtree of a node should have a key bigger than its key and all elements in the left subtree of a node should have a key less than its key. for example, consider this binary tree:

4 / \ 2 6 / \ / \ 1 9 3 7

it has the property that for every node x of $T$ that is not a leaf, the key of x is larger or equal than the key of the left child and less or equal than the key of the right child, but it's not a BST since 3 is in the right subtree of root but its key is less than the key of root.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ According to CLRS BST is a tree where the given a node $x$ and a node $y$ which belongs to the left sub-tree of $x$ then $key(y)≤key(x)$. (Chapter 12.1) $\endgroup$
    – Yos
    Commented Jun 16, 2017 at 9:25
  • $\begingroup$ @Yos You're right, I'm sorry I thought it was part of all definitions of BST. but if identical keys are allowed, then search time will be $O(n)$ in a worst case (when all keys are equal). $\endgroup$
    – Karegar
    Commented Jun 16, 2017 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.