2
$\begingroup$

Using the definition of a leaf as being an internal node with no children (both children are external nodes), how can I find the total number of leaves for all binary trees with n internal nodes, for any n.

I know the number of binary trees with n internal nodes is given by Catalan numbers however I can't work out how to enumerate all $C_n$ trees for each n to find number of leaves (as defined above).

Thanks for any help!

$\endgroup$
  • $\begingroup$ "Using the definition of a leaf as being an internal node with no children" This doesn't make sense. A leaf has no children and internal node is typically called a branch and has children. $\endgroup$ – N8tron May 31 '18 at 18:50
  • $\begingroup$ @N8tron I took that from Sedgewick and Flajolet, regardless in this case I'm considering a leaf an internal node with both children external nodes $\endgroup$ – user2201609 May 31 '18 at 19:08
  • $\begingroup$ Okay now that I've caught onto your notation. I'm going to share a link that can help that make more sense to people using the standard definitions. Note though that even S & F use the standard definition in their appendix ;) algo.inria.fr/flajolet/Publications/book.pdf $\endgroup$ – N8tron May 31 '18 at 19:24
  • $\begingroup$ @N8tron thanks, I should've made it more clear I was not looking at the standard definition $\endgroup$ – user2201609 May 31 '18 at 19:31
  • $\begingroup$ Do you want to consider isomorphism classes of rooted trees or any tree? or do you want to consider isomorphism classes at all? $\endgroup$ – N8tron May 31 '18 at 19:34

Your Answer

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

Browse other questions tagged or ask your own question.