**This is <s>intermediate between an answer, and</s> a long comment on Max Alekseyev's post.**  

As discussed in the comments below his answer, there is a flaw in his post, so that it gives a lower bound.  But there's a straightforward way to progress past the flaw.  Unfortunately, there's a further obstruction that I do not see how to proceed beyond.  

**Begin with a slight generalization.**  Start with a single node of length $s$, and build a random tree as follows:
* Select a leaf node $n$ uniformly at random.  Call its weight $w$.  
* Select $p\in[0,1]$ uniformly at random.  
* Attach two children to $n$ of weight $pw$ and $(1-p)w$.  

Your problem asks: if $s=1$, what is the largest weight of a leaf, when there are $n$ nodes?  Call this random variable $X^0_n$; in the general case, that length scales to $sX^0_n$.  

**As Max Alekseyev noticed, there is a natural recurrence structure to this tree.**  For notational convenience, suppose $n+1$ nodes.  The root node has two children, weighted $P$ and $1-P$; let there be $K$ and $n-K$ nodes beneath each (inclusive); then $K$ is chosen uniformly from $\{0,1,\dots,n\}$.  Take two iid copies of $X^0$, called $X^1$ and $X^2$.  Since leaf nodes must descend from the children of the root, $$(X_{n+1}^0|K,P)=\max(PX^1_K,(1-P)X^2_{n-K})$$  

**To proceed exactly, introduce a CDF-like function.**  Let $F_n(t)=\mathbb{P}\left[{X_n\leq\frac{1}{t}}\right]$; then \begin{align*}
(n+1)F_{n+1}(t)&=(n+1)\mathbb{P}\left[{X_n^0\leq\frac{1}{t}}\right] \\
&=\sum_{k=0}^n{\int_0^1{\mathbb{P}\left[{\max(PX^1_K,(1-P)X^2_{n-K})\leq\frac{1}{t}}\middle|{K=k,|P-p|\leq dp}\right]}} \\
&=\sum_{k=0}^n{\int_0^1{\mathbb{P}\left[{pX^1_k\leq\frac{1}{t}}\wedge{(1-p)X^2_{n-k}\leq\frac{1}{t}}\right]\,dp}} \\
&=\sum_{k=0}^n{\int_0^1{F_k(pt)F_{n-k}((1-p)t)\,dp}}
\end{align*}  

**The finite sum is a discrete convolution, and can be eliminated by passing to generating functions.**  Let $\mathcal{F}(t,z)=\sum_{n=0}^{\infty}{F_n(t)z^n}$.  Then $$\mathcal{F}(pt,z)\mathcal{F}((1-p)t,z)=\sum_{n=0}^{\infty}{\sum_{k=0}^n{F_k(pt)F_{n-k}((1-p)t)z^n}}$$  Integrating in $p$ recovers the recurrence from above, which simplifies to \begin{gather*}
\frac{\mathcal{F}(t,z)}{\partial z}=\int_0^1{\mathcal{F}(pt,z)\mathcal{F}((1-p)t,z)\,dp} \\
\mathcal{F}(t,0)=F_0(t)=\begin{cases}t&0<t\leq1\\0&\text{otherwise}\end{cases}
\end{gather*}  Note that $F_n(t)=0$ for $t<0$, so that we can extend the bounds of integration to $\mathbb{R}$ without effect.  

**The other integral can _almost_ be eliminated via the Fourier transform.**  Now let $\mathcal{G}(u,z)=\int_\mathbb{R}{\mathcal{F}(t,z)e^{uti}\,dt}$.  Then \begin{align*}
\frac{\partial\mathcal{G}(u,z)}{\partial z}&=\int_\mathbb{R}{\frac{\mathcal{F}(t,z)}{\partial z}e^{uti}\,dt} \\
&=\iint_{\mathbb{R}^2}{e^{upti}\mathcal{F}(pt,z)\cdot e^{u(1-p)ti}\mathcal{F}((1-p)t,z)\,d^2(p,t)} \\
&=\iint_{\mathbb{R}^2}{e^{\alpha ui}\mathcal{F}(\alpha,z)\cdot e^{\beta ui}\mathcal{F}(\beta,z)\,\frac{d^2(\alpha,\beta)}{\alpha+\beta}}
\end{align*}  If the $\alpha+\beta$ in the denominator could be removed (say, by tweaking the definition of $F_n$ and using an analogous integral transform), then the last line would simplify to $\mathcal{G}(u,z)^2$.  

**Unfortunately, I do not know an integral transform that avoids the extra $\alpha+\beta$ term.**  Nevertheless, let me indulge and sketch the the argument after such a gap were filled, although I'm sure the structure of the argument will come as little surprise to most readers.  

Suppose the necessary integral transform has $L^2$ adjoint given by kernel $\hat{I}$ and define $$\alpha(u)=\int_1^\infty{\frac{\hat{I}(t)}{t^2}\,dt}$$  (Yes, one probably needs a little care to show that this integral converges.  But it's ultimately just calculating an explicit integral.)  

In the OP, you ask for \begin{align*}
\mathbb{E}[X_n]&=\int_0^1{\mathbb{P}[X_n\leq t]\,dt} \\
&=\int_0^1{F_n\left(\frac{1}{t}\right)\,dt} \\
&=\int_1^\infty{F_n(u)\,\frac{du}{u^2}}
\end{align*} which has generating function $$\mathcal{E}(z)=\int_1^\infty{\mathcal{F}(t,z)\,\frac{dt}{t^2}}=\int_\mathbb{R}{\overline{\alpha(u)}\mathcal{G}(u,z)\,du}$$  Thus it suffices to have an explicit formula for $\mathcal{G}$.  

From the known value of $\mathcal{F}(t,0)$, $$\mathcal{G}(u,0)=\frac{1-e^{ui}(1-ui)}{u^2}$$  The differential equation above is then an ODE that uniquely determines $\mathcal{G}$ as some locally-$C^{\infty}$ function $$\mathcal{G}(u,z)=\sum_{n=0}^\infty{g_n(u)z^n}$$  Comparing coefficients of $z^n$, $$\mathbb{E}[X_n]=\int_\mathbb{R}{\overline{\alpha(u)}g_n(u)\,du}$$ and so the problem reduces to estimating an explicit integral.