Binary Search Tree

A binary search tree is a binary tree storing keys (or key-value entries) at its internal nodes and satisfying the following property:

• If we let $u$, $v$, and $w$ be three nodes such that $u$ is in the left subtree of $v$ and $w$ is in the right subtree of $v$. We have that $key(u)\le key(v)\le key(w)$.
• External nodes do not store items.
• An In-order traversal of binary search tree visits the keys in increasing order.