Consider binary trees where each node is either a leaf or possesses exactly two child nodes (left and right, which we consider different).
How many different trees are there on n nodes?
For example:
- 3 nodes -> 1 tree,
- 4-> 0 tree,
- 5 -> 2 trees,
- 6 -> 0 tree,
- 7 -> 5 trees,
- and so on ...
There is any formular for this sequence? I have found formular for all possible binary tree (Catalan number) but I'm searching for full tree.
In a "full" tree, there are an odd number of nodes and every second node in order is a leaf.
If you remove all these leaves, you are left with a binary tree that might not be full. For any (maybe not full) binary tree, there is exactly one way to add a leaf at the start, the end, and between each pair of nodes, to make a full binary tree.
So there is a 1-1 correspondence between binary trees with n nodes, and full trees with 2n+1 codes.
C(n) -- the catalan number -- is the number of binary trees with n nodes, and also therefore the number of "full" trees with 2n+1 nodes.
The number of full binary trees with n nodes is therefore C((n-1)/2). Since you can't have half a node, the answer is 0 when n is even.