3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? What is $n$? $\endgroup$ – Yuval Filmus Aug 30 '13 at 20:55
  • 2
    $\begingroup$ How do you define height? (there are two common definitions differing by $1$) $\endgroup$ – Yuval Filmus Aug 30 '13 at 21:04
  • $\begingroup$ I forgot to to say number of nodes, it is $n$. $\endgroup$ – user9909 Aug 31 '13 at 9:33
  • $\begingroup$ problem setter was not very precise, I think for definition of height we consider height of root to be zero $\endgroup$ – user9909 Aug 31 '13 at 9:42
  • $\begingroup$ this might help you: stackoverflow.com/a/13093274/550393 $\endgroup$ – 2cupsOfTech Apr 10 '14 at 15:44
1
$\begingroup$

Take the height $h$ as the length of the longest root to leaf path. After fixing the root, we count the number in two cases:

  1. both left and right subtrees are of height $h$. number of trees $=A_h^2$
  2. only one subtree has height $h$. number of trees $=2 \cdot A_h \cdot (A_0+A_1+...+A_{h-1})$

$$ A_{h+1} = A_h^2 + 2 \cdot A_h \cdot (A_0+A_1+...+A_{h-1}) $$

$\endgroup$
  • $\begingroup$ I think this is the right answer, but can we get a closed form ? $\endgroup$ – user9909 Aug 31 '13 at 9:46
  • $\begingroup$ This is not the exact anwer to the question, since it does not restrict the number of nodes to $n$. By the way, for a closed form look at A001699 $\endgroup$ – Parham Sep 1 '13 at 0:20
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ what is $A^{i} _{j}$ and what does $i$ stands for? $\endgroup$ – user9909 Aug 31 '13 at 9:40
  • $\begingroup$ as I said, It was a test question, and the correct answer was $ 2^h \choose n - 2^h +1 $ can you explain this ? $\endgroup$ – user9909 Aug 31 '13 at 9:50
  • $\begingroup$ The author of the question must have had a different definition of binary trees in mind. The link agrees with me that $A_h - A_{h-1}$ is the number of binary trees of height $h$. $\endgroup$ – Yuval Filmus Aug 31 '13 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.