All Possible Full Binary Trees

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:

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

# 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[TreeNode | None]:
        if n % 2 == 0:
            return []  # Full binary trees must have an odd number of nodes
        
        if n == 1:
            return [TreeNode(0)]

        result = []
        for i in range(1, n, 2):  # Iterate through odd numbers for left subtree size
            left_size = i
            right_size = n - 1 - i

            left_trees = self.allPossibleFBT(left_size)
            right_trees = self.allPossibleFBT(right_size)

            for left_tree in left_trees:
                for right_tree in right_trees:
                    root = TreeNode(0)
                    root.left = left_tree
                    root.right = right_tree
                    result.append(root)

        return result


# Example Usage and Visualization (for n=7)
# The following code is for demonstration and does not directly contribute to the solution.
# It helps visualize the output for a specific input.

def visualize_tree(root: TreeNode | None) -> list[int | None]:
    """Helper function to visualize the tree structure as a list."""
    if not root:
        return [None]

    result = [root.val]
    left_subtree = visualize_tree(root.left)
    right_subtree = visualize_tree(root.right)

    result.extend(left_subtree)
    result.extend(right_subtree)
    return result

# Example Usage
n = 7
solution = Solution()
trees = solution.allPossibleFBT(n)

# Visualize the first few trees (optional)
for i in range(min(5, len(trees))):
    tree_visualization = visualize_tree(trees[i])
    print(f"Tree {i+1}: {tree_visualization}")

Explanation:

1. Base Case: If n is 1, return a list containing a single node with value 0.
2. Odd Number Check: If n is even, return an empty list since a full binary tree must have an odd number of nodes.
3. Recursive Calls: Iterate through possible sizes for the left subtree (i). The remaining nodes form the right subtree.
   • Recursively generate all possible full binary trees for the left subtree using self.allPossibleFBT(i). These are stored in left_trees.
   • Recursively generate all possible full binary trees for the right subtree using self.allPossibleFBT(n - 1 - i). These are stored in right_trees.
4. Combining Subtrees: For each combination of left and right subtrees, create a new root node with value 0, set the left and right subtrees accordingly, and add the resulting tree to the result list.
5. Return: Return the result list containing all possible full binary trees.

Example with n = 3:

1. allPossibleFBT(3):
   • Loop with i = 1:
     • left_size = 1, right_size = 1
     • left_trees = [TreeNode(0)]
     • right_trees = [TreeNode(0)]
     • Create a root node with value 0, left child from left_trees, and right child from right_trees.
     • Add the resulting tree to result.
2. Return result.

Example with n = 7:

With n = 7, the function explores various combinations of left and right subtree sizes:

• Left size = 1, Right size = 5
• Left size = 3, Right size = 3
• Left size = 5, Right size = 1

For each of these combinations, the function recursively generates the possible trees and combines them. The visualize_tree function is used to represent each tree as a list for printing purposes.

Big O Runtime Analysis:

The time complexity is determined by the number of possible full binary trees for a given n, which grows exponentially. Specifically, the number of full binary trees with n nodes is related to the Catalan number. The Catalan number C(n) grows asymptotically as 4^n / (nsqrt(pin)). Due to the nature of Catalan numbers, the total runtime is O(4^n / (n^(3/2))). The recursion generates all possible binary trees, so it explores a number of trees related to the Catalan number.

Big O Space Analysis:

The space complexity is dominated by the storage of the resulting trees. In the worst case, the number of trees grows exponentially with n (related to Catalan numbers). The depth of the recursion also contributes to the space complexity, which is O(n) in the worst case (a skewed tree). Overall, the space complexity is O(4^n / (n^(3/2))), representing the space required to store the generated trees. In addition, call stack space will be O(n).