All Possible Full Binary Trees

Problem Statement

In this task, you are required to construct all the possible variations of a full binary tree with a specified number of nodes, n. Every node in each tree needs to have a value of 0 (Node.val == 0). A full binary tree is defined as a binary tree wherein every node either has two children or no child. The output of this function should be a list where each item represents one possible full binary tree; here each tree is depicted from its root node. The collection of trees can be returned in any order.

Examples

Example 1

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

Approach and Intuition

Given the task of generating all full binary trees with n nodes, where n is an odd integer from 1 to 20, let's explore the intuition and a step-by-step method to tackle this problem:

1. Base Case Consideration:

   • When n = 1, there is only one tree possible which is simply the root node with no children. This is because a full binary tree with one node cannot have any children.

2. Recursive Build:

   • For any odd number n > 1, the root node subtracts one node from the total count, leaving n-1 nodes to be distributed among the left and right subtrees.
   • To maintain the full binary tree property, both left and right subtrees must themselves be full binary trees and the number of nodes in them must also be odd.

3. Dividing Nodes:

   • Iterate through odd numbers from 1 to n-1 to allocate nodes for the left subtree (l). The right subtree (r) will then have n - 1 - l nodes. Both l and r must be odd to ensure they can form full binary trees.
   • For each valid division (where l and r are both odd), recursively generate all possible left and right subtrees.

4. Combining Trees:

   • For each combination of left and right subtree rooted at the current node, create a new tree and add it to the list of full binary trees.

5. Efficiency Optimization:

   • The recursive approach can be optimized using memoization to store results for particular values of n that have been computed already, thereby saving redundant calculations.

The key to solving this problem lies in understanding the recursive structure of full binary trees, ensuring that each subtree itself adheres to the full binary tree constraints, and effectively combining these subtrees in all possible ways around a new root to form larger trees.

Solutions

class Solution {
public:
    vector<TreeNode*> generateAllFBT(int totalNodes) {
        if (totalNodes % 2 == 0) {
            return {};
        }
            
        vector<vector<TreeNode*>> trees(totalNodes + 1);
        trees[1].push_back(new TreeNode(0));
            
        for (int nodes = 3; nodes <= totalNodes; nodes += 2) {
            for (int leftNodes = 1; leftNodes < nodes - 1; leftNodes += 2) {
                int rightNodes = nodes - 1 - leftNodes;
                for (auto leftTree : trees[leftNodes]) {
                    for (auto rightTree : trees[rightNodes]) {
                        TreeNode* currentNode = new TreeNode(0, leftTree, rightTree);
                        trees[nodes].push_back(currentNode);
                    }
                }
            }
        }
            
        return trees[totalNodes];
    }
};