Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!nachum
From: nachum@m.cs.uiuc.edu
Newsgroups: comp.theory
Subject: Re: Full Binary Trees
Message-ID: <37800019@m.cs.uiuc.edu>
Date: 21 Nov 90 19:25:00 GMT
Lines: 16
Nf-ID: #R:<9011202221.AA08268@irt.watson.i:-39:m.cs.uiuc.edu:37800019:000:628
Nf-From: m.cs.uiuc.edu!nachum    Nov 21 13:25:00 1990


/* Written  4:21 pm  Nov 20, 1990 by BURGARD@DBNINF5.BITNET in m.cs.uiuc.edu:comp.theory */
/* ---------- "Full Binary Trees" ---------- */
I am interested in the following problem:

  What is the order of the average depth of the leafs of full binary
  trees with n leafs?
  ...
  - Conjecture:  A(n) is sublinear, e.g. O(n^c) with c<1
  ...
/* End of text from m.cs.uiuc.edu:comp.theory */

Your conjecture is correct.  It is O(sqrt(n)), by results in Knuth's vol.
1, sect. 2.3.4.5 on "external path length".  (See also my paper with S.
Zaks, "Patterns in Trees", in Discrete Applied Math, vol. 25, pp. 241ff.,
result 3.5.1.)