Justify the following running time
The book is correct, because $b\leq 2n$, so you visit no more than $3n$ nodes, which is $O(n)$, and $b\leq 2n$ because no node has more than two leaves. You correctly say that $b$ grows proportional to $n$, which is exactly the key.

Just for clarity, Big-Oh notation means "grows proportional to, ignoring constant factors" (roughly), which is why we say that $3n\in O(n)$, even though one is a multiple of the other, and $6n^2+3n+42\in O(n^2)$ and $42e^n\in O(e^n)$, for example. 

(actually, $O(n)$ means, "is not more than $cn$". For "is proportional to $n$", use $\Theta(n)$ instead of $O(n)$).