It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log(n))$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0).
I have an algorithm that traverses every path in the tree (beginning at the root) but stops after traversing $k$ nodes (the parameter $k$ is a configurable parameter which is independent of the size of the tree $n$).
For any tree $T$ with $depth(T) > k$, the algorithm will miss some nodes of the tree. I would like to bound the probability of my algorithm missing a large number of nodes.
Formalizing it: let $T$ be a randomly built binary search tree of $n$ nodes. I would like to calculate the probability for a node to have depth larger than $k$, as a function of $n$ and $k$.