HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Number of binary trees with given height

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numberheightwithtreesbinarygiven

Problem

I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$).

Edit: I forgot to add the number of nodes.

Solution

I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees.

I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$).

Let $A_h$ be the number of binary trees with height at most $h$. Then $A_{-1} = 1$ and $A_h = 1 + A_{h-1}^2$. This is A003095. The number of trees with height exactly $h$ is $A_h - A_{h-1}$, which is A001699. Both sequences have asymptotics of the form $\alpha^{2^h}$ for some $\alpha > 1$.

Context

StackExchange Computer Science Q#14043, answer score: 5

Revisions (0)

No revisions yet.