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). 

Lets take the 100K values and 1m records. The root split could be, the records with the max value goes right, all other records go left. Then the next split on the left says the records with the max value of those 99,999 values go right, all other records go left. And so on. In this case it peels off one value, and all records with that value, at each split.

That is an extreme example but it illustrates the point. The split could be the min, max or anywhere in between. The number of records at each value is what is important.

You can research the answer to your tree by exporting the tree which will show you the splits and the split statistic for each node.