The node of a binary tree is called a single child if it has a parent but does not have a sibling. The root is by definition not considered a single child.

Let $T$ be a binary tree of size $n$, and let $k$ be the number of vertices in $T$ that are single children. Is it true that if $\frac{k}{n}\leq \frac{1}{2}$ then the height of $T$ is $O(\log n)$?

  • 1
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Oct 11 '20 at 17:48

You can construct a tree with no single children which has height $(n-1)/2$: Path tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.