Approach 1: Recursion
Intuition and Algorithm
Let be the list of all possible full binary trees with nodes.
Every full binary tree with 3 or more nodes, has 2 children at its root. Each of those children
right are themselves full binary trees.
Thus, for , we can formulate the recursion: [All trees with left child from and right child from , for all ].
Also, by a simple counting argument, there are no full binary trees with a positive, even number of nodes.
Finally, we should cache previous results of the function so that we don't have to recalculate them in our recursion.
Time Complexity: . For odd , let . Then, , the -th catalan number; and (the complexity involved in computing intermediate results required) is bounded by . However, the proof is beyond the scope of this article.
Space Complexity: .
Analysis written by: @awice.