Solution


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 left and 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.

Complexity Analysis

  • 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.