Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key $k$ in a binary search tree ends up in a leaf. Consider three sets: $A$, the keys to the left of the search path; $B$, the keys on the search path; and $C$, the keys to the right of the search path. Professor Bunyan claims that any three keys $a \in A$, $b \in B$, and $c \in C$ must satisfy $a \leq b \leq c$. Give a smallest possible counterexample to the professor’s claim.

In this example, we are searching for key $k = 1$ and the shaded nodes represent our path from root to leaf. This search path gives us $A = \{\}$, $B = \{4, 2, 1\}$ and $C = \{3\}$. Because $3 < 4$, Professor Bunyan’s claim that $a \leq b \leq c$ does not hold.

The following LaTeX code was used to generate the above binary search tree:

\documentclass[border = 5pt, tikz]{standalone}

\begin{document}
\begin{tikzpicture}[
  every node/.style = {minimum width = 2em, draw, circle},
  shade/.style = {fill=black!15},
  level/.style = {sibling distance = 30mm/#1}
  ]
  \node [shade] {4}
  child {node [shade] {2}
        child {node [shade] {1}}
        child {node {3}}
        }
  child {edge from parent[draw = none]};
\end{tikzpicture}
\end{document}