All Possible Full Binary Trees - Leetcode Solution

Problem Statement:

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.

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

Example:

Input: 7 Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0]]

Explanation:

There are two trees with 7 nodes. One has a root node with two children, each of which has two children, and the other has a root node with one child, which has two children, each of which has two children.

Solution:

This problem can be solved using recursion. We can start by creating a root node and then recursively building the left and right subtrees.

We can iterate over all even integers less than N and for each integer i, we can create all possible full binary trees for the left and right subtrees with i nodes and N-i-1 nodes respectively.

For each root node, we can combine all possible left and right subtrees to get all possible full binary trees with N nodes.

We can implement the above approach using a recursive function allPossibleFBT() which takes an integer N as input and returns a list of all possible full binary trees with N nodes.

Here is the Python code for the solution:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
class Solution:
    def allPossibleFBT(self, N: int) -> List[TreeNode]:
        # base case: N is even or less than 1
        if N % 2 == 0 or N < 1:
            return []
        # base case: N is 1
        if N == 1:
            return [TreeNode(0)]
        # list to store all possible trees
        trees = []
        # iterate over all even integers less than N
        for i in range(1, N, 2):
            # create all possible left subtrees with i nodes
            leftSubtrees = self.allPossibleFBT(i)
            # create all possible right subtrees with N-i-1 nodes
            rightSubtrees = self.allPossibleFBT(N-i-1)
            # combine all possible left and right subtrees
            for leftSubtree in leftSubtrees:
                for rightSubtree in rightSubtrees:
                    # create root node with value 0
                    root = TreeNode(0)
                    root.left = leftSubtree
                    root.right = rightSubtree
                    # add new tree to list of all trees
                    trees.append(root)
        return trees

Time Complexity:

The time complexity of this solution is O(2^N) because there can be a maximum of 2^N possible full binary trees with N nodes.

Space Complexity:

The space complexity of this solution is O(2^N) because we are returning a list of all possible full binary trees with N nodes.

1