Finding the height of all nodes in a forest
First of all, it depends a bit how you can access your data to say which algorithms works best. 

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases}
\left(\max_{u\text{ child of }v}\text{height}(u)\right)+1 &amp; \text{if $u$ is not a leaf} \\
\hskip4ex 0 &amp; \text{otherwise}
\end{cases}.
$$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you know that you have average degree less than two (and therefore you can test for roots in linear time).