# Max depth for a decision tree in sklearn

I know there is a partial answer here but my question is slightly different. I have implemented a decision tree in sklearn. Say I have $2^n$ different values for a feature, with just one feature. I was expecting that a good decision tree should be able to keep the depth at or below $n$. Let's say the $2^n$ values for the features are indexed ($1 \dots 2^n$), if I make a split in the middle, that is the most effective way, and I can get a leaf with just one element at the end of a a n-deep tree.

Of course, it could be less, if, for example, I only have two categories, and all the elements below $2^{n-1}$ are in one class, and the other elements in the other class. But, in the worst case, I thought I should have depth $n$. However, when I implemented a solution for just around 1 million examples with one feature that has about 100,000 values, I got a tree with depth 125! (and I was expecting about 17).

Why is that?

There is an assumption in the statement if I make a split in the middle. The assumption is the tree will always split at the middle value = the median value so half the values go right and the other half go left. The split could be anywhere. And importantly the split focuses on the number of records at each value (think histogram).