question
How many distinct binary tree shapes exist for n nodes?
ex. For 3 nodes there are 5 distinct shapes:
ex. For 3 nodes there are 5 distinct shapes:
Calculate number of tree shapes for small values of n and find a pattern.
count(0) = 1
c(1) = c(0)*c(0) = 1
c(2) = c(0)*c(1) + c(1)*c(0) = 2
c(3) = c(0)*c(2) + c(1)*c(1) + c(2)*c(0) = 5
c(4) = c(0)*c(3) + c(1)*c(2) + c(2)*c(1) + c(3)*c(0) = 14
This can be generalized to: c(n) = c(0)*c(n - 1) + c(1)*c(n - 2) + ... + c(n -1)*c(0)
The pattern is in fact well known as the Catalan numbers and can be rewritten as:
c(n) = (2n)! / (n + 1)!n!
Thoughts or alternate solution? Let us know in the comments below!
c(1) = c(0)*c(0) = 1
c(2) = c(0)*c(1) + c(1)*c(0) = 2
c(3) = c(0)*c(2) + c(1)*c(1) + c(2)*c(0) = 5
c(4) = c(0)*c(3) + c(1)*c(2) + c(2)*c(1) + c(3)*c(0) = 14
This can be generalized to: c(n) = c(0)*c(n - 1) + c(1)*c(n - 2) + ... + c(n -1)*c(0)
The pattern is in fact well known as the Catalan numbers and can be rewritten as:
c(n) = (2n)! / (n + 1)!n!
Thoughts or alternate solution? Let us know in the comments below!