Problem Description

You need to generate all possible full binary trees that contain exactly n nodes.

A full binary tree is a special type of binary tree where every node has either 0 children (leaf node) or exactly 2 children. There are no nodes with just one child.

Given an integer n, your task is to:

• Create all structurally unique full binary trees with n nodes
• Each node in every tree must have Node.val == 0
• Return a list containing the root node of each possible tree
• The trees can be returned in any order

For example:

• If n = 1, there's only one possible tree: a single node
• If n = 3, there's one possible tree: a root with two leaf children
• If n = 5, there are two possible trees with different structures

Note that full binary trees can only have an odd number of total nodes. This is because every internal node adds exactly 2 children, so starting from 1 node (the root), you can only have 1, 3, 5, 7, ... nodes.

The solution uses a recursive approach with memoization. It works by:

1. If n = 1, returning a single node tree
2. For n > 1, trying all possible ways to split nodes between left and right subtrees
3. For each split where left subtree has i nodes, the right subtree has n - 1 - i nodes (accounting for the root)
4. Recursively generating all possible left and right subtrees
5. Combining each left subtree with each right subtree to create complete trees
6. Using @cache decorator to avoid recalculating the same subtree structures

Intuition

The key insight is recognizing that a full binary tree has a recursive structure - every full binary tree consists of a root node with two subtrees that are themselves full binary trees.

First, let's observe an important property: full binary trees can only have an odd number of nodes. Why? Because we start with 1 node (the root), and every time we expand a leaf into an internal node, we add exactly 2 new nodes. So we go from 1 → 3 → 5 → 7... always odd numbers.

Now, how do we build all possible full binary trees with n nodes? We can think of it as a distribution problem. We have n total nodes:

• 1 node is used for the root
• The remaining n - 1 nodes must be distributed between the left and right subtrees

Since both subtrees must also be full binary trees (and thus have odd numbers of nodes), we need to split n - 1 into two odd numbers. This means we try:

• Left: 1 node, Right: n - 2 nodes
• Left: 3 nodes, Right: n - 4 nodes
• Left: 5 nodes, Right: n - 6 nodes
• And so on...

For each valid split, we recursively generate all possible full binary trees for the left side and all possible trees for the right side. Then we create new trees by combining each left possibility with each right possibility.

The beauty of this approach is that smaller subproblems (trees with fewer nodes) are solved first and can be reused when building larger trees. For instance, all trees with 3 nodes will be computed once and reused whenever we need a subtree of size 3. This naturally suggests using memoization to cache results and avoid redundant calculations.

The base case is straightforward: when n = 1, there's only one possible tree - a single node with no children.

Learn more about Tree, Recursion, Memoization, Dynamic Programming and Binary Tree patterns.

Solution Approach

The implementation uses memoization search (dynamic programming with recursion) to efficiently generate all possible full binary trees.

Core Algorithm:

The solution defines a recursive function dfs(n) that returns a list of all possible full binary trees with n nodes:

1. Base Case: When n = 1, return a list containing a single node [TreeNode()].

2. Recursive Case: For n > 1, enumerate all valid ways to split nodes between left and right subtrees:

   • Loop through possible left subtree sizes: i = 0, 1, 2, ..., n-1
   • Calculate corresponding right subtree size: j = n - 1 - i (accounting for the root node)
   • Note: Since full binary trees must have odd nodes, only odd values of i and j will produce valid trees

3. Tree Construction: For each valid split (i, j):

   • Recursively get all possible left subtrees: dfs(i)
   • Recursively get all possible right subtrees: dfs(j)
   • Create new trees by combining each left subtree with each right subtree using nested loops
   • Each combination creates a new root node with TreeNode(0, left, right)

4. Memoization: The @cache decorator automatically caches results of dfs(n) for each value of n. When the same subtree size is needed again, the cached result is returned immediately instead of recalculating.

Data Structures:

• TreeNode: Standard binary tree node with val, left, and right attributes
• List: Stores all possible tree roots for each subproblem
• Cache (hidden): The @cache decorator maintains a dictionary mapping input values to results

Time Complexity Analysis:

The number of full binary trees with n nodes is the (n-1)/2-th Catalan number, which grows exponentially. With memoization, each unique subproblem is solved only once, but the total work is still proportional to the sum of all Catalan numbers up to (n-1)/2.

Space Complexity:

The space is used for storing all the generated trees and the recursion stack. The dominant factor is the storage of all possible trees, which is also related to Catalan numbers.

Example Walkthrough

Let's walk through generating all full binary trees with n = 5 nodes.

Step 1: Initial Call We call dfs(5) to find all full binary trees with 5 nodes.

Step 2: Enumerate Splits For n = 5, we have 4 nodes to distribute between left and right subtrees (5 - 1 for root = 4). We try each possible split where i + j = 4:

• i = 0, j = 4: Invalid (0 is even, can't form a full binary tree)
• i = 1, j = 3: Valid ✓
• i = 2, j = 2: Invalid (2 is even)
• i = 3, j = 1: Valid ✓
• i = 4, j = 0: Invalid (4 is even)

Step 3: Process First Valid Split (i=1, j=3)

Get left subtrees with 1 node:

• dfs(1) returns [TreeNode(0)] - just a single node

Get right subtrees with 3 nodes:

• dfs(3) needs to find all trees with 3 nodes
• For n = 3, we split 2 nodes: only i=1, j=1 is valid
• dfs(1) returns [TreeNode(0)] for both left and right
• Combine to create one tree with 3 nodes:

      0
     / \
    0   0

Combine left(1) and right(3):

• We have 1 left option × 1 right option = 1 tree:

      0
     / \
    0   0
       / \
      0   0

Step 4: Process Second Valid Split (i=3, j=1)

Get left subtrees with 3 nodes:

• dfs(3) returns the cached result from Step 3: one tree with structure 0(0,0)

Get right subtrees with 1 node:

• dfs(1) returns [TreeNode(0)] - just a single node

Combine left(3) and right(1):

• We have 1 left option × 1 right option = 1 tree:

      0
     / \
    0   0
   / \
  0   0

Step 5: Return Result dfs(5) returns a list containing both trees:

Tree 1:

    0
   / \
  0   0
     / \
    0   0

Tree 2:

    0
   / \
  0   0
 / \
0   0

Key Observations:

• The function only explores odd-numbered splits since even numbers can't form full binary trees
• dfs(1) and dfs(3) are computed once and cached for reuse
• Each recursive call builds upon smaller subproblems
• The final result contains all structurally unique full binary trees with exactly 5 nodes

Solution Implementation

Time and Space Complexity

The time complexity is O(2^n / sqrt(n)) and the space complexity is O(2^n / sqrt(n)), where n is the number of nodes.

Time Complexity Analysis:

• This problem generates all possible full binary trees with n nodes
• A full binary tree must have an odd number of nodes, and the number of such trees with n nodes is the (n-1)/2-th Catalan number
• The Catalan number C_k = (2k)! / ((k+1)! * k!) asymptotically equals 4^k / (k^(3/2) * sqrt(π))
• For n nodes where n = 2k + 1, we have C_k ≈ 4^k / (k * sqrt(πk)) = 2^(2k) / (k * sqrt(πk))
• Since k = (n-1)/2, this becomes approximately 2^(n-1) / ((n-1)/2 * sqrt(π(n-1)/2)) which simplifies to O(2^n / sqrt(n))
• Each tree construction involves constant work due to memoization, so the total time complexity is O(2^n / sqrt(n))

Space Complexity Analysis:

• The memoization cache stores all unique full binary trees for each value from 1 to n
• The total number of trees stored is proportional to the sum of Catalan numbers up to (n-1)/2
• The dominant term is the largest Catalan number, which is O(2^n / sqrt(n))
• Each tree has O(n) nodes, but since we're counting the number of distinct trees rather than total nodes across all trees, the space complexity for storing all trees is O(2^n / sqrt(n))
• The recursion depth is at most O(n), which is negligible compared to the cache storage
• Therefore, the overall space complexity is O(2^n / sqrt(n))

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting that Full Binary Trees Only Have Odd Number of Nodes

A very common mistake is not recognizing early that full binary trees can only have an odd number of nodes. This leads to unnecessary computation and incorrect results.

Pitfall Code:

@cache
def generate_trees(num_nodes: int) -> List[Optional[TreeNode]]:
    if num_nodes == 1:
        return [TreeNode()]
  
    result = []
    # Wrong: iterating through all values instead of just odd ones
    for left_nodes in range(1, num_nodes):
        right_nodes = num_nodes - 1 - left_nodes
        # This will try to generate trees with even number of nodes
        left_subtrees = generate_trees(left_nodes)
        right_subtrees = generate_trees(right_nodes)
        # ... rest of the code

Why it's problematic: This attempts to generate trees with even numbers of nodes, which is impossible for full binary trees. It wastes computation time and may cause infinite recursion or stack overflow.

Solution: Add an early check for even numbers and iterate only through odd values:

if num_nodes % 2 == 0:
    return []

for left_nodes in range(1, num_nodes - 1, 2):  # Step by 2 to get only odd numbers
    right_nodes = num_nodes - 1 - left_nodes

2. Creating Shared Node References Instead of New Nodes

Another critical mistake is reusing the same node object across different trees, leading to trees that share nodes and create invalid structures.

Pitfall Code:

@cache
def generate_trees(num_nodes: int) -> List[Optional[TreeNode]]:
    if num_nodes == 1:
        # Wrong: returning the same node reference for all single-node trees
        single_node = TreeNode()
        return [single_node]  # This same node will be used in multiple trees!

Why it's problematic: When this cached result is used multiple times, the same node object appears in different positions across different trees. Modifying one tree could affect others, and the tree structure becomes invalid with cycles or shared subtrees.

Solution: Always create new node instances:

if num_nodes == 1:
    return [TreeNode()]  # Creates a new node each time

# And in the combination loop:
for left_tree in left_subtrees:
    for right_tree in right_subtrees:
        # Always create a new root node
        root = TreeNode(0, left_tree, right_tree)
        result.append(root)

3. Incorrect Node Count Distribution

A subtle but common error is miscalculating how to distribute nodes between left subtree, right subtree, and root.

Pitfall Code:

for left_nodes in range(1, num_nodes, 2):  # Wrong upper bound
    right_nodes = num_nodes - left_nodes  # Forgot to account for root node

Why it's problematic: This doesn't account for the root node in the calculation. If you have n total nodes and allocate i to the left subtree, the right subtree should get n - 1 - i nodes (not n - i), because one node is used as the root.

Solution: Correctly account for all nodes:

for left_nodes in range(1, num_nodes - 1, 2):  # Ensure at least 1 node for right
    right_nodes = num_nodes - 1 - left_nodes  # -1 accounts for the root node

4. Not Using Memoization or Using It Incorrectly

Without memoization, the solution recalculates the same subtree structures repeatedly, leading to exponential time complexity.

Pitfall Code:

def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
    # No memoization - recalculates same subtrees multiple times
    def generate_trees(num_nodes: int) -> List[Optional[TreeNode]]:
        # ... recursive logic without caching

Why it's problematic: For example, when generating trees with 7 nodes, generate_trees(3) might be called multiple times from different recursive paths, each time rebuilding the same structures from scratch.

Solution: Use @cache decorator or maintain a manual memoization dictionary:

@cache  # Automatically memoizes the function
def generate_trees(num_nodes: int) -> List[Optional[TreeNode]]:
    # ... recursive logic

Note: When using @cache with functions that return mutable objects (like tree nodes), be careful about modifying the returned trees, as they're shared across calls.