Algorithm to find the two closest elements in a BST
In most common models of computation, it cannot be ensured to find the two closest elements in a binary search tree (BST) in $O(\log n)$ time or, in fact, in $o(n)$ time. Here $n$ is the number of elements in BST and $o(n)$ is the little $o$-notation.

The idea is simple. There must be enough running time for an algorithm to access at least about half of the elements.  

Here is an detailed explanation. It is not rigorous;  to make it rigorous we will need an explicit adversary argument as well as a more detailed formal specification of the model of computation.



Let us fix some model of computation $M$ in which at most $c$ elements can be accessed in a unit time of computation for some constant $c$. In fact, $c$ is usually 1 or 2. 

For the sake of contradiction, suppose algorithm $Alg$ can find the two closest elements in a BST of $n$ element in $o(n)$ time. So for constant $\dfrac1{3c}$, there exists a constant $n_0&gt;0$ such that $A$ can find the two closest element in no more than $\dfrac1{3c}n$ time for all $n&gt;n_0$.

Now let $n_1&gt;\max(n_0, 6)$. Let $Alg$ runs on a BST with $n_1$ nodes for some time that is no more than $\dfrac1{3c}n_1$. Then $A$ has accessed at most $\dfrac{1}{3c}n_1\cdot c=\dfrac {n_1}3$ elements.
Let $a_1, a_2, \cdots, a_{n_1}$ be the elements in the BST in nondecreasing order. There must be at least 2 adjacent elements in that nondecreasing list of all elements none of which have been accessed by the algorithm. Those two elements mights be closer to each other than any pair of elements among the elements that have been accessed by $Alg$. That means, $Alg$ may not have found the two closest elements. This is a contradiction.





Exercise. Find the two closest elements in a binary search tree with left-child pointers, right-child pointers and parent pointers in $O(1)$ working space.