# All Possible Full Binary Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/all-possible-full-binary-trees)
Canonical: https://scaleengineer.com/dsa/problems/all-possible-full-binary-trees
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Tree, Binary Tree
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## Problem
Given an integer `n`, return _a list of all possible **full binary trees** with_ `n` _nodes_. Each node of each tree in the answer must have `Node.val == 0`.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in **any order**.

A **full binary tree** is a binary tree where each node has exactly `0` or `2` children.

**Example 1:**

![](https://assets.glich.co/dsa/all-possible-full-binary-trees/image0.png) 

**Input:** n = 7
**Output:** [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

**Example 2:**

**Input:** n = 3
**Output:** [[0,0,0]]

**Constraints:**

* `1 <= n <= 20`

# Approaches
## Brute-Force Recursion
This approach directly translates the recursive definition of a full binary tree into a function. A full binary tree with `n` nodes is formed by a root, a left full binary subtree, and a right full binary subtree. The total number of nodes `n` must be odd. If `n=1`, it's a single node. For `n > 1`, we can partition the remaining `n-1` nodes into a left subtree with `i` nodes and a right subtree with `n-1-i` nodes. Since both subtrees must also be full binary trees, `i` and `n-1-i` must be odd. We can iterate through all possible odd values for `i`, recursively generate all possible left and right subtrees, and combine them.
**Time:** O(2^n). This is a loose upper bound. The function is called for the same `n` multiple times, leading to an exponential number of calls. For example, `allPossibleFBT(7)` calls `allPossibleFBT(5)` and `allPossibleFBT(3)` multiple times through different call paths. This repeated computation makes the algorithm very slow. · **Space:** O(n * 2^n). The space is required for the recursion call stack and to store the generated trees. The number of trees and their total nodes grows exponentially.
**Pros:** Simple to understand and implement as it directly follows the mathematical definition.
**Cons:** Extremely inefficient due to a massive number of redundant computations.; The time complexity is exponential, making it infeasible for even moderately larger values of `n` (though it might pass for the given constraints, it's a poor approach).; Can lead to a `StackOverflowError` for larger `n` due to deep recursion, although not an issue for `n <= 20`.
### Explanation
The core idea is to break down the problem of finding trees with `n` nodes into smaller subproblems. We observe the inherent recursive structure: any full binary tree with more than one node has a root, a left subtree, and a right subtree, both of which must also be full binary trees. This leads to a straightforward recursive algorithm.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> result = new ArrayList<>();
        // A full binary tree must have an odd number of nodes.
        if (n % 2 == 0) {
            return result;
        }
        // Base case: a tree with 1 node is just a single node.
        if (n == 1) {
            result.add(new TreeNode(0));
            return result;
        }

        // Iterate through all possible numbers of nodes for the left subtree.
        // The number of nodes in a subtree must also be odd.
        for (int i = 1; i < n; i += 2) {
            int j = n - 1 - i; // Remaining nodes for the right subtree.
            
            List<TreeNode> leftSubtrees = allPossibleFBT(i);
            List<TreeNode> rightSubtrees = allPossibleFBT(j);

            // Combine every possible left subtree with every possible right subtree.
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- The function `allPossibleFBT(n)` is defined to return a list of all full binary trees with `n` nodes.
- **Base Case 1:** If `n` is an even number, it's impossible to form a full binary tree. Return an empty list.
- **Base Case 2:** If `n` is 1, the only possible tree is a single node. Return a list containing just this node.
- **Recursive Step:** For an odd `n > 1`, iterate through all possible odd numbers for the left subtree's node count, let's call it `i`, from `1` to `n-2`.
- For each `i`, the right subtree must have `j = n - 1 - i` nodes.
- Recursively call `allPossibleFBT(i)` to get all possible left subtrees.
- Recursively call `allPossibleFBT(j)` to get all possible right subtrees.
- Create a new tree for every combination of a left subtree and a right subtree. A new root node is created, and its `left` and `right` children are set to the pair of subtrees.
- Add each newly formed tree to a result list.
- Return the final list of trees.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the simple recursion by recognizing that the same subproblems (generating trees for a specific number of nodes `k`) are solved multiple times. We can optimize this by using memoization, which means caching the results of these subproblems. A hash map can be used as a cache to store the list of trees for each number of nodes `k` once it's computed. This is a top-down dynamic programming approach.
**Time:** O(N * C_k), where N is the number of nodes `n`, and C_k is the k-th Catalan number with k = (n-1)/2. The number of full binary trees with `n` nodes is `C_((n-1)/2)`. The total work is proportional to the total number of nodes across all generated trees, as each subproblem is solved only once. · **Space:** O(N * C_k), where N is the number of nodes `n`, and C_k is the k-th Catalan number with k = (n-1)/2. The space is dominated by the memoization cache, which stores all the generated trees for subproblems from 1 to `n`.
**Pros:** Significantly more efficient than simple recursion by avoiding re-computation of subproblems.; Guarantees that the solution for each subproblem `allPossibleFBT(k)` is computed only once.; Feasible for the given constraints (`n <= 20`).
**Cons:** Uses recursion, which has a slight overhead compared to an iterative solution.; The space complexity is high as it needs to store all the generated trees for all subproblems.
### Explanation
The inefficiency of the brute-force recursion comes from re-calculating the solutions for the same subproblems. By storing the result for each `n` after computing it the first time, we can avoid this redundant work. This technique is called memoization.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        List<TreeNode> result = new ArrayList<>();
        if (n % 2 == 0) {
            return result;
        }
        if (n == 1) {
            result.add(new TreeNode(0));
            memo.put(1, result);
            return result;
        }

        for (int i = 1; i < n; i += 2) {
            int j = n - 1 - i;
            List<TreeNode> leftSubtrees = allPossibleFBT(i);
            List<TreeNode> rightSubtrees = allPossibleFBT(j);

            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        memo.put(n, result);
        return result;
    }
}
```
### Algorithm
- Use a cache, like a `HashMap<Integer, List<TreeNode>>`, to store the results for each number of nodes `n`.
- The recursive function `allPossibleFBT(n)` first checks if the result for `n` is already in the cache. If yes, it returns the cached list.
- If not in the cache, it performs the same computation as the brute-force approach:
  - Handle base cases for even `n` and `n=1`.
  - Loop through possible left subtree sizes `i`.
  - Recursively call the function for `i` and `n-1-i`. These calls will also utilize the cache.
  - Combine the subtrees to form new trees.
- Before returning, store the newly computed list of trees in the cache with `n` as the key.
- This ensures that the trees for any given number of nodes `k` are computed only once.

## Bottom-Up Dynamic Programming
This is an iterative version of the memoized approach, often called bottom-up dynamic programming. Instead of starting from `n` and recurring downwards (top-down), we build the solutions for an increasing number of nodes, from 1 up to `n`. This avoids recursion altogether and builds the solution from the smallest subproblems to the largest.
**Time:** O(N * C_k), where N is `n`, and C_k is the k-th Catalan number with k = (n-1)/2. The complexity is identical to the memoized approach, as the same number of fundamental computations are performed. · **Space:** O(N * C_k), where N is `n`, and C_k is the k-th Catalan number with k = (n-1)/2. The DP table stores all intermediate results, which is the same amount of data as the memoization cache.
**Pros:** Avoids recursion overhead and the risk of stack overflow, making it slightly more performant and robust.; The iterative structure can be easier to analyze and debug.; Considered the standard and most efficient DP approach for this type of problem.
**Cons:** The space complexity is high, similar to the memoization approach.; Can be slightly less intuitive to write than the direct recursive solution for some.
### Explanation
By building solutions iteratively, we can eliminate recursion. We solve for smaller numbers of nodes first and use those results to construct solutions for larger numbers of nodes. This is a classic dynamic programming technique that is often more efficient in practice than its recursive counterpart due to the absence of function call overhead.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return new ArrayList<>();
        }
        // dp[i] stores the list of all FBTs with i nodes.
        List<List<TreeNode>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }

        // Base case: a tree with 1 node.
        dp.get(1).add(new TreeNode(0));

        // Build up solutions for 3, 5, ..., n nodes.
        for (int num_nodes = 3; num_nodes <= n; num_nodes += 2) {
            // Iterate through all possible left subtree sizes.
            for (int left_nodes = 1; left_nodes < num_nodes; left_nodes += 2) {
                int right_nodes = num_nodes - 1 - left_nodes;

                List<TreeNode> leftSubtrees = dp.get(left_nodes);
                List<TreeNode> rightSubtrees = dp.get(right_nodes);

                for (TreeNode left : leftSubtrees) {
                    for (TreeNode right : rightSubtrees) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        dp.get(num_nodes).add(root);
                    }
                }
            }
        }
        return dp.get(n);
    }
}
```
### Algorithm
- Create a DP table, `dp`, which is a list of lists of `TreeNode`. `dp[i]` will store all possible full binary trees with `i` nodes.
- Handle the `n` is even case upfront by returning an empty list.
- Initialize the base case: `dp[1]` contains a single tree with one node.
- Iterate for the number of nodes `i` from `3` to `n` with a step of 2.
- Inside this loop, to compute `dp[i]`, iterate through all possible odd left subtree sizes `j` from `1` to `i-2`.
- The right subtree size will be `k = i - 1 - j`.
- Retrieve the lists of pre-computed subtrees from `dp[j]` and `dp[k]`.
- Combine every left subtree from `dp[j]` with every right subtree from `dp[k]`. For each pair, create a new root, attach the subtrees, and add the new tree to `dp[i]`.
- After the loops complete, `dp[n]` will hold the final answer.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private List < TreeNode >[] f ; public IList < TreeNode > AllPossibleFBT ( int n ) { f = new List < TreeNode >[ n + 1 ]; return Dfs ( n ); } private IList < TreeNode > Dfs ( int n ) { if ( f [ n ] != null ) { return f [ n ]; } if ( n == 1 ) { return new List < TreeNode > { new TreeNode () }; } List < TreeNode > ans = new List < TreeNode >(); for ( int i = 0 ; i < n - 1 ; ++ i ) { int j = n - 1 - i ; foreach ( var left in Dfs ( i )) { foreach ( var right in Dfs ( j )) { ans . Add ( new TreeNode ( 0 , left , right )); } } } f [ n ] = ans ; return ans ; } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < TreeNode >[] f ; public List < TreeNode > allPossibleFBT ( int n ) { f = new List [ n + 1 ]; return dfs ( n ); } private List < TreeNode > dfs ( int n ) { if ( f [ n ] != null ) { return f [ n ]; } if ( n == 1 ) { return List . of ( new TreeNode ()); } List < TreeNode > ans = new ArrayList <>(); for ( int i = 0 ; i < n - 1 ; ++ i ) { int j = n - 1 - i ; for ( var left : dfs ( i )) { for ( var right : dfs ( j )) { ans . add ( new TreeNode ( 0 , left , right )); } } } return f [ n ] = ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < TreeNode *> allPossibleFBT ( int n ) { vector < vector < TreeNode *>> f ( n + 1 ); function < vector < TreeNode *> ( int ) > dfs = [ & ]( int n ) -> vector < TreeNode *> { if ( f [ n ]. size ()) { return f [ n ]; } if ( n == 1 ) { return vector < TreeNode *> { new TreeNode ()}; } vector < TreeNode *> ans ; for ( int i = 0 ; i < n - 1 ; ++ i ) { int j = n - 1 - i ; for ( auto left : dfs ( i )) { for ( auto right : dfs ( j )) { ans . push_back ( new TreeNode ( 0 , left , right )); } } } return f [ n ] = ans ; }; return dfs ( n ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def allPossibleFBT ( self , n : int ) -> List [ Optional [ TreeNode ]]: @ cache def dfs ( n : int ) -> List [ Optional [ TreeNode ]]: if n == 1 : return [ TreeNode ()] ans = [] for i in range ( n - 1 ): j = n - 1 - i for left in dfs ( i ): for right in dfs ( j ): ans . append ( TreeNode ( 0 , left , right )) return ans return dfs ( n )
```