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

Author

Alois P. Heinz, Jun 29 2020

Keywords

• nonn

Comments

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

Examples

			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
.
		

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

Crossrefs

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

Programs

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 *)

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 }.