# Depth of binary tree with few single children

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

• What do you think? Oct 11 '20 at 17:48

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