A binary search tree (BST) is a binary tree with labelled vertices such that for any vertex all vertices in the left subtree are less than it’s label and all vertices in the right subtree are greater.
To build the tree, order the vertices then select the root via: \[ \left \lfloor \frac{{min} + {max}}{2} \right \rfloor \] Repeat for each subtree.
As an example, a 14 element BST can be visualised as below
\begin{document}
\begin{tikzpicture}[thick,level/.style = {sibling distance = 60mm/#1}]
\node {7}
child {
node {3}
child {
node {1}
child[missing]
child {node {2}}
}
child {
node {5}
child {node {4}}
child {node {6}}
}
}
child {
node {11}
child {
node {9}
child {node {8}}
child {node {10}}
}
child {
node {13}
child {node {12}}
child {node {14}}
}
};
\end{tikzpicture}
\end{document}The height of a binary search tree can be found via the following \[ h = \left\lceil \log_2(n+1) \right\rceil \] This height defines the maximum number of comparisons required to find an stored element.