A335921 Total height of all binary search trees with n internal nodes.

0, 1, 4, 14, 50, 178, 644, 2347, 8624, 31908, 118768, 444308, 1669560, 6298280, 23842032, 90531032, 344702646, 1315726218, 5033357852, 19294463682, 74099098212, 285056401796, 1098314920968, 4237879802726, 16373796107092, 63341371265892, 245315823125496

Offset

0,3

Comments

Empty external nodes are counted in determining the height of a search tree.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Wikipedia, Binary search tree

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Formula

a(n) = Sum_{k=0..n} k * A335919(n,k) = Sum_{k=0..n} k * A335920(n,k).

a(n) is odd <=> n in { A083420 }.

Example

a(3) = 14 = 3 + 3 + 2 + 3 + 3:
.
          3         3        2        1         1
         / \       / \      / \      / \       / \
        2   o     1   o    1   3    o   3     o   2
       / \       / \      ( ) ( )      / \       / \
      1   o     o   2     o o o o     2   o     o   3
     / \           / \               / \           / \
    o   o         o   o             o   o         o   o
.

Maple

g:= n-> `if`(n=0, 0, ilog2(n)+1):
b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n, k)*k, k=g(n)..n):
seq(a(n), n=0..35);

Mathematica

g[n_] := If[n == 0, 0, Floor@Log2[n] + 1];
b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
a[n_] := Sum[T[n, k]*k, {k, g[n], n}];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Apr 26 2022, after Alois P. Heinz *)

Crossrefs

Cf. A083420, A316944, A335919, A335920, A335922.

Sequence in context: A120747 A229314 A055099 * A153367 A211304 A047065

Adjacent sequences: A335918 A335919 A335920 * A335922 A335923 A335924

Keyword

nonn

Author

Alois P. Heinz, Jun 29 2020

Status

approved