Skip to main content
3 of 3
Commonmark migration

Conditions for a binary tree being balanced

Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.

If you disprove, the counterexample should consist of an infinite sequence of trees in the family rather than just a single tree, because the property is asymptotic.

A. There is a constant $c$ so that for each node of the tree, the difference in height between the two sub-trees is at most $c$.

B. There is constant $c$ so that the average height of each node in the tree is at most $c \log n$.

Now I proved A using induction, and I know how to disprove B using a single example, but I don't know how to do so using infinitely many examples.

Gil
  • 49
  • 7