A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST.

1, 1, 2, 1, 6, 6, 4, 1, 94, 114, 116, 94, 60, 28, 8, 1, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 5193067630, 6939692682, 8948546308, 11120136162, 13299362332, 15286065700, 16859410792, 17813777994, 17999433372

Offset: 0

Author

Viktar Karatchenia, Oct 13 2019

Keywords

• nonn
• look

Comments

For any BST node p, p.left.value < p.value and p.right.value > p.value provided that the left (right) node exists.

Examples

			a(1) = 1 - the trivial tree having 1 node.
a(2) = 2 - two trees: one {1,2} rooted at node 1, and {2,1} - at 2.
a(3) = 1 - one BST tree of height 1 with edges {1,2}, {2,3} rooted at the node 2.
      2
    1   3
a(4) = 6. Optimal BST height is 2. When the root is 1, the remaining nodes {2,3,4} can form 1 subtree having height 1. Taking 2 as the root, 1 must go to the left, and {3,4} - right; there can be 2 trees on {3,4}. The cases for root 4,3 are symmetric. Thus, a(4) = 2*(1+1*2) = 6. The 6 BSTs of the optimal height 2 are: ({1,3},{3,2},{3,4}), ({2,1},{2,3},{3,4}), ({2,1},{2,4},{4,3}), ({3,4},{3,2},{2,1}), ({3,4},{3,1},{1,2}), ({4,2},{2,1},{2,3}).
a(5) = 1+1+2*2 = 6. Height=2. Nodes 1,5 cannot be the root, because the remaining 4 nodes cannot be compressed into a BST of height 1. Node 2 as the root implies {3,4,5} must follow to the right (left) producing 1 tree. Node 4 similarly adds 1 more BST. Finally, 3 as the root allows the formation of 2 trees consisting of {1,2} to the left of the root, and 2 trees of {4,5} to the right giving 2*2 = 4 trees.
a(6) = 4. Here height = 2. The nodes 1,2,5,6 can't be the root. When rooting at the third node, {1,2} will form 2 trees, and {4,5,6} to the right will make 1 possible tree of height 1. The node 4 is similar to 3. In total, a(6) = 2*1*2 = 4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1023
• Wikipedia, Binary search tree
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A000225, A000523, A076615, A195581, A244108, A335919, A335920.

Programs

Julia

# after C++ program
const _cache = Dict{Tuple{Int, Int}, Int}()
function f(k::Int, level::Int)
    (k >= 1 << level) && return 0
    level = min(k, level)
    haskey(_cache, (k, level)) && return _cache[(k, level)]
    r = 0
    for root in 1:k
        left  = root == 1 ? 1 : f(root - 1, level - 1)
        right = root == k ? 1 : f(k - root, level - 1)
        r += left * right
    end
    return _cache[k, level] = r
end
BinaryIntegerLength(n) = n == 0 ? 1 : floor(Int, log2(n)) + 1
[f(n, BinaryIntegerLength(n)) for n in 1:40] |> println # Peter Luschny, Oct 14 2019

Maple

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:
a:= n-> b(n, ilog2(n)+1):
seq(a(n), n=0..42);  # Alois P. Heinz, Jun 28 2020

Mathematica

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]];
a[n_] := b[n, Floor@Log[2, n]+1];
a /@ Range[0, 42] (* Jean-François Alcover, Nov 15 2020, after Alois P. Heinz *)

Formula

a(n) = 1 when n = 2^m - 1, m > 0 because the optimal BST represents a full binary tree thus precisely 1 tree is possible.

a(n) = 2^(m-1) when n = 2^m - 2, m > 1. Here the BST is full BST minus 1 node, which must be at the last level. The last level of a full BST has 2^(m-1) nodes. Once the "missing" node is chosen at the last level, there is only 1 BST.

a(n) = f(n, 1+floor(log_2(n))) where f(k, level) is 0 when there are too many nodes (k >= 2^ level), otherwise f(k, level) = Sum_{root=1..n}(root=1 ? 1 : f(root-1, level-1)) * (root=k ? 1 : f(k-root, level-1))).

a(n) = A335919(n,max(0,A000523(n)+1)) = A335920(n,max(0,A000523(n)+1)). - Alois P. Heinz, Jun 29 2020

Extensions

a(0)=1 prepended by Alois P. Heinz, Jun 28 2020