# Prove $T$ is a BST iff 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$

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.

• 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. – fade2black Jun 16 '17 at 9:03
• @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? – Yos Jun 16 '17 at 9:06
• 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. – fade2black Jun 16 '17 at 9:19

## 1 Answer

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.

• 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) – Yos Jun 16 '17 at 9:25
• @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). – Karegar Jun 16 '17 at 10:14