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

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

1 Answer 1

2
$\begingroup$

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

$\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.