# How many different (full/complete) in-order binary-trees do exist?

Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-trees do exist?
Q3: How many different full binary-trees do exist?

For Q1 I was able to find a solution, by using the catalan number formula:
c(n) = (2n)! / ((n + 1)! * n!)c(4) = 14.

For Q2 and Q3 however I was not able to find an answer to those problems.
Do general formulas for n elements even exist?

Definition of full and complete.

• There is exactly one complete binary tree with any given number of leaves. Commented Jun 3, 2020 at 22:00
• Full binary trees are also enumerated by Catalan numbers (with a shift). Commented Jun 3, 2020 at 22:00
• (Note that stackexchange encourages answering your own question. Consider using a "spoiler".) Commented Jun 4, 2020 at 7:42

Q1: How many different binary-trees do exist?
A1: c(n) = (2n)! / ((n + 1)! * n!)c(4) = 14

Q2: How many different complete binary-trees do exist?
A2: Exact one:

;       (3)        L0: full
;      / | \
;   (2)  |  (4)    L1: full
;   /|   |   |
; (1)|   |   |     L2: not full (Node 2 is missing right child)
;  | |   |   |
;  1 2   3   4     Complete?: Yes, because all (but last) levels are full.


Q3: How many different full binary-trees do exist?
A3: If n is odd: c((n-1)/2) else 0. n = 4 therefore 0. Reference

Thanks to YuvalFilmus for the help!