Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers.

You can also view it as a recurrence:

  f(1) = 1
  f(n) = 2*f(n - 1) + 1 = 2^n - 1

But your binary search tree example is more intuitive.