What is the average size of a jump in a binary tree?
Consider a binary search tree with layers $0,\ldots,h$, where layer $\ell$ contains $2^\ell$ nodes. The left child of a node $x$ is located next to it (at distance 1). If $x$ is at layer $\ell$, then its left subtree contain $2^{h-\ell}-1$ nodes, and so the right child of $x$ is at distance $2^{h-\ell}$. These observations are illustrated in the figure:



Here $h = 3$, and the root ($\ell = 0$) has a left child at distance $1$ and a right child at distance $2^{h-\ell} = 8$.

We will calculate the average size of a jump in a random root-to-leaf path. This corresponds to searching for a random leaf.

The expected jump at level $\ell$ is thus $\frac{1+2^{h-\ell}}{2}$. Since there are $h$ jumps overall (at levels $0$ to $h-1$), the average jump is
$$
\frac{1}{h} \sum_{\ell=0}^{h-1} \frac{1+2^{h-\ell}}{2} =
\frac{1}{2} + \frac{1 + \cdots + 2^{h-1}}{h} =
\frac{1}{2} + \frac{2^h-1}{h}.
$$
Since the number of nodes in the tree is $n := 2^{h+1}-1$, the average jump is $\Theta(n/\log n)$. The same holds for the number of leaves $m := 2^h$.