Random walks on Complete Binary Trees
This answers a previous version of the question, in which the goal was to prove that with high probability, $\max |H_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$ for some constant $C &gt; 0$.

When a particular walker is not at the root, it has a probability of 2/3 to go down a step, and a probability of 1/3 to go up a step. This is where $n/3$ comes from. However, when it is at the root, it always goes down. This suggests comparing $H_i$ to a sum of $n$ i.i.d. variables whose distribution is $+1$ w.p. $2/3$ and $-1$ w.p. $1/3$. Indeed, if $X_i$ is a variable with that distribution, then $H_i$ stochastically dominates $X_i$. Hence it suffices to show that
$$
\mathbb{P}\left(\max_{i \in [m]} X_i \geq \tfrac{n}{3} + C\sqrt{n\ln m}\right) \geq 1-\frac{1}{m}.
$$
(More formally, we can construct a coupling of the $H_i$ and $X_i$ in which $H_i \geq X_i$.)

Up to an affine transformation, the distribution of $X_i$ is binomial, so it should be easy to obtain whatever bound you wish. You can take a look at Lower bounds on binomial and Poisson tails: anapproach via tail conditional expectations by Pelekis, for example.