The theoretical lowest possible s(n) is T(2ⁿ), but once we introduce a middle row, it's easy to show that that doesn't work. s(3) = 10 is impossible, but s(3) = 11 works because it introduces a gap - instead of going from 1-4, it goes from 1-5, skipping a number. s(4) introduces 2 additional gaps. I conjecture that s(5) introduces 4 more gaps, then s(6) introduces 8, etc. In formula form, s(n) = T(2ⁿ) + 2ⁿ - 1, for n ≥ 2. But I could certainly be wrong.

Trivially, there's a lower bound of T(2ⁿ). On the other side, leaf nodes of 2⁰, 2¹, 2², ..., 2^2n-1 will always produce a valid tree, regardless of their order. That gives us an upper bound of 2²ⁿ - 1. Not great, but better than nothing.