0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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