Skip to main content
1 of 3
Gil
  • 49
  • 7

Binary Tree disprove question

Prove or disprove for each of the following two traits, Is a family of trees that fulfill the the feature is balanced.

in case of disprove, the opposite example should contain an infinite series of trees in the family, and not just a single tree because the feature 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 B is disprove by using example but I don't know how to do it with infinite one.

Gil
  • 49
  • 7