login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328349 Number of binary search trees (BST) on n nodes which have the same height as the optimal BST. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

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

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

EXAMPLE

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 to form 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.

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

PROG

(C++)

#include<bits/stdc++.h>

using namespace std;

map<pair<int, int>, int64_t> _cache;

int64_t f(const int k, int level) {

    if (k >= 1ll << level) return 0;

    level = min(k, level);

    const auto p = make_pair(k, level);

    const auto d = _cache.find(p);

    if (d != _cache.end()) return d->second;

    int64_t r = 0;

    for (auto root = 1; root <= k; ++root) {

        const auto left = root == 1 ? 1 : f(root - 1, level - 1),

            right = root == k ? 1 : f(k - root, level - 1);

        r += left * right;

    }

    assert(r);

    return _cache[p] = r;

}

int main() {

    for (auto n = 1; n <= 70; ++n) {

        const auto level = 1 + static_cast<int>(log2(n));

        const auto c = f(n, level);

        cout << n << '\t' << c << '\n';

    }

    return 0;

}

(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

CROSSREFS

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

Sequence in context: A052121 A193895 A193561 * A117965 A111646 A342965

Adjacent sequences:  A328346 A328347 A328348 * A328350 A328351 A328352

KEYWORD

nonn,look

AUTHOR

Viktar Karatchenia, Oct 13 2019

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 26 05:46 EDT 2021. Contains 348256 sequences. (Running on oeis4.)