A note on the Horton-Strahler number for random trees (Q1338782)

The Horton-Strahler number \(S(T)\) of a binary tree \(T\) is defined recursively as follows. If \(T\) is the trivial tree then \(S(T)= 1\); and if \(T\) is a non-trivial tree with main branches \(L\) and \(R\) then \(S(T)\) equals \(\max\{S(L),S(R)\}\) if \(S(L)\neq S(R)\) and \(S(L)+1\) otherwise. Let \(S_ n\) denote the Horton-Strahler number of a random equiprobable binary tree with \(n\) nodes. The authors extend known results by showing that there exists a constant \(C>0\) such that \(Pr\{| S_ n- \log_ 4 n|\geq x\}\leq C\cdot 4^{-x}\) for all \(x>0\).