1
$\begingroup$

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)$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What do you think? $\endgroup$
    – Yuval Filmus
    Commented Oct 11, 2020 at 17:48
  • $\begingroup$ Why worry about the case of the root ? Does that make a difference ? $\endgroup$
    – user16034
    Commented May 12, 2022 at 7:59

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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