This answers the version of the question in which the goal is to show that with high probability, $\max |H_i - \frac n 3| \leq C\sqrt{n\ln m}$ for some constant $C$.
Since $|H_{i+1}-H_i| \le 1$, you can use Azuma's inequality (via Doob's martingale) to upper bound the probability of deviation from the mean, and so obtain your required bound, once we show that the expectation of $H_n$ is very close to $\frac{n}{3}$.
To this end, let $X_i$ be a random variable equal to $+1$ with probability $2/3$ and to $-1$ with probability $1/3$, and couple $H_i - H_{i-1}$ to the $X_i$: if $H_{i-1} = 0$ then $H_i = 1$, and otherwise $H_i = H_{i-1} + X_i$. Let $Y_i$ be a random variable equal to $+2$ if $H_{i-1} = 0$ and $X_i = -1$, and equal to $0$ otherwise, so that $H_i = H_{i-1} + X_i + Y_i$. In total, $H_n = \sum_{i=1}^n (X_i + Y_i)$.
In order to calculate $\mathbb{E}[H_n]$, notice first that $\mathbb{E}[X_i] = \frac13$. For calculating $\mathbb{E}[Y_i]$, let us notice that the event "$H_{i-1}=0$" is independent of the event "$X_i=-1$". Therefore, if we let $Z_i$ be the indicator of $H_i = 0$, then $\mathbb{E}[Y_i] = \frac23 \mathbb{E}[Z_i]$. Defining $Z = \sum_{i=1}^\infty Z_i$, we have
$$
\frac{n}{3} \leq \mathbb{E}[H_n] \leq \frac{n}{3} + \frac{2}{3} \mathbb{E}[Z].
$$
Let $a_k$ be the expected number of visits to the root if starting at a node at depth $k$ (so $a_0 = \mathbb{E}[Z]$), let $p = 1/3$, and let $q = 1-p = 2/3$. Then $a_k$ satisfies the following recurrence:
$$
a_0 = 1 + a_1, \quad a_k = p a_{k-1} + q a_{k+1}.
$$
Let us prove inductively that $a_k = (p/q)^k + a_{k+1}$. This holds for $k = 0$. Given that $a_{k-1} = (p/q)^{k-1} + a_k$, we have
$$
a_k = pa_{k-1} + qa_{k+1} = p(p/q)^{k-1} + pa_k + qa_{k+1}.
$$
This implies that $qa_k = p(p/q)^{k-1} + qa_{k+1}$, and so $a_k = (p/q)^k + a_{k+1}$, as claimed.
When $p < 1/2$, we know that $\mathbb{E}[H_n] \longrightarrow \infty$, and so $a_k \longrightarrow 0$ (this requires proof). Therefore
$$
a_0 = \sum_{k=0}^\infty (p/q)^k = \frac{1}{1-p/q} = \frac{q}{q-p}.
$$
(Similarly, $a_k = (p/q)^k \frac{q}{q-p}$.) In our case, $a_0 = 2$, and so
$$
\frac{n}{3} \leq \mathbb{E}[H_n] \leq \frac{n+4}{3}.
$$