Problem Description

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 the value 0.

A full binary tree is a binary tree where every node has either 0 or 2 children. You may return the answer in any order.

• Input: An integer n representing the number of nodes.
• Output: A list of all possible full binary trees with n nodes, where each node has value 0.

Constraints:

• 1 <= n <= 20
• Each tree node must have either 0 or 2 children.
• All node values are 0.
• Each tree structure must be unique; do not reuse nodes between trees.
• Return all valid trees (not just one).

Thought Process

At first, you might think about generating all possible binary trees with n nodes and then filtering out the ones that are not full. However, that approach is inefficient, as the number of binary trees grows rapidly with n.

Instead, we can use the definition of a full binary tree to build only valid trees:

• Every node has either 0 or 2 children.
• Therefore, the number of nodes in a full binary tree is always odd (since adding two children increases the node count by 2).

We can recursively construct all trees by:

• For each possible split of nodes between left and right subtrees, recursively generate all full binary trees for those subtree sizes.
• Combine each pair of left and right subtrees with a new root node.

Solution Approach

We use a recursive, memoized approach to generate all full binary trees:

1. Base Case: If n == 1, the only possible tree is a single node. Return a list containing a single-node tree.
2. Odd n Only: If n is even, return an empty list (since full binary trees can only have an odd number of nodes).
3. Recursive Construction:
   • For all odd numbers left_nodes from 1 to n-2 (step 2), do:
   • Let right_nodes = n - 1 - left_nodes.
   • Recursively generate all full binary trees with left_nodes and right_nodes nodes.
   • For each combination of a left and right subtree, create a new root node and attach the subtrees.
4. Memoization: Store the result for each n so that we do not recompute the same result multiple times.
5. Return: Return the list of all constructed trees for n.

This approach ensures that:

• Only valid full binary trees are constructed.
• Duplicate computation is avoided using memoization.

Example Walkthrough

Let's walk through the case where n = 5:

1. Since n is odd and greater than 1, we try all possible splits:
   • left_nodes = 1, right_nodes = 3
   • left_nodes = 3, right_nodes = 1
2. For each split, recursively generate all full binary trees for left_nodes and right_nodes:
   • For left_nodes = 1, only one tree: single node.
   • For right_nodes = 3:
     • Splits: 1|1 (since 3-1=2, only odd split is 1 and 1).
     • Both left and right are single-node trees.
     • Combine them into a root with two single-node children.
   • Similarly, for left_nodes = 3 and right_nodes = 1, swap the above.
3. For each pair of left and right subtrees, create a new root and attach them.
4. In total, there are two unique full binary trees with 5 nodes.

Time and Space Complexity

Brute-force Approach:

• Generating all binary trees and filtering for full ones would be exponential in n (super-exponential, as the number of binary trees grows as Catalan numbers).

• The number of unique full binary trees with n nodes is the (n-1)/2th Catalan number, which grows exponentially but much slower than the number of all binary trees.
• Each subproblem is solved only once due to memoization.
• Time Complexity: O(C_n), where C_n is the Catalan number for n nodes.
• Space Complexity: O(C_n) for storing all trees and the memoization cache.

For n <= 20, this approach is efficient and practical.

Summary

To generate all possible full binary trees with n nodes:

• We use recursion to build trees only for odd n (since full binary trees have an odd number of nodes).
• We split the remaining nodes between left and right subtrees in all possible ways, recursively building each subtree.
• Memoization ensures efficiency by storing previously computed results.
• This approach elegantly leverages the properties of full binary trees and recursion, making the solution both efficient and easy to reason about.

Code Implementation

from typing import List, Optional

# 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]]:
        memo = {}

        def build(n):
            if n in memo:
                return memo[n]
            if n == 1:
                return [TreeNode(0)]
            if n % 2 == 0:
                return []
            res = []
            for left_nodes in range(1, n, 2):
                right_nodes = n - 1 - left_nodes
                for left in build(left_nodes):
                    for right in build(right_nodes):
                        root = TreeNode(0)
                        root.left = left
                        root.right = right
                        res.append(root)
            memo[n] = res
            return res

        return build(n)
      

/**
 * 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:
    unordered_map<int, vector<TreeNode*>> memo;
    vector<TreeNode*> allPossibleFBT(int n) {
        if (memo.count(n)) return memo[n];
        vector<TreeNode*> res;
        if (n == 1) {
            res.push_back(new TreeNode(0));
            return res;
        }
        if (n % 2 == 0) return res;
        for (int left_nodes = 1; left_nodes < n; left_nodes += 2) {
            int right_nodes = n - 1 - left_nodes;
            vector<TreeNode*> left_trees = allPossibleFBT(left_nodes);
            vector<TreeNode*> right_trees = allPossibleFBT(right_nodes);
            for (auto left : left_trees) {
                for (auto right : right_trees) {
                    TreeNode* root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    res.push_back(root);
                }
            }
        }
        memo[n] = res;
        return res;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() { val = 0; }
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;

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> res = new ArrayList<>();
        if (n == 1) {
            res.add(new TreeNode(0));
            return res;
        }
        if (n % 2 == 0) return res;
        for (int left_nodes = 1; left_nodes < n; left_nodes += 2) {
            int right_nodes = n - 1 - left_nodes;
            List<TreeNode> left_trees = allPossibleFBT(left_nodes);
            List<TreeNode> right_trees = allPossibleFBT(right_nodes);
            for (TreeNode left : left_trees) {
                for (TreeNode right : right_trees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        memo.put(n, res);
        return res;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function(n) {
    const memo = {};

    function build(n) {
        if (memo[n]) return memo[n];
        if (n === 1) return [new TreeNode(0)];
        if (n % 2 === 0) return [];
        let res = [];
        for (let left_nodes = 1; left_nodes < n; left_nodes += 2) {
            let right_nodes = n - 1 - left_nodes;
            let left_trees = build(left_nodes);
            let right_trees = build(right_nodes);
            for (let left of left_trees) {
                for (let right of right_trees) {
                    let root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    res.push(root);
                }
            }
        }
        memo[n] = res;
        return res;
    }

    return build(n);
};