# Solution For All Possible Full Binary Trees

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:

“`python

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.

## Step by Step Implementation For All Possible Full Binary Trees

/** * 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 ListallPossibleFBT(int N) { // create an empty list to store all possible full binary trees List list = new ArrayList (); // if N is odd, then there can be only one possible full binary tree if (N % 2 == 1) { // create a full binary tree with root as 1 TreeNode root = new TreeNode(1); // recursively generate all possible full binary trees with N nodes generateFBT(root, 1, N, list); } return list; } // generate all possible full binary trees with given number of nodes public void generateFBT(TreeNode root, int numNodes, int N, List list) { // if number of nodes in current full binary tree == N, then add it to the list if (numNodes == N) { list.add(root); return; } // recursively generate left and right subtrees TreeNode left = new TreeNode(1); TreeNode right = new TreeNode(1); // connect left and right subtrees to the root root.left = left; root.right = right; // recursively generate all possible full binary trees with numNodes+2 nodes generateFBT(left, numNodes+1, N, list); generateFBT(right, numNodes+1, N, list); } }

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def allPossibleFBT(self, N: int) -> List[TreeNode]: # if N is odd, then there will always be at least one possible full binary tree # if N is even, then there will be no possible full binary trees # therefore, we only need to consider the case when N is odd if N % 2 == 0: return [] # base case: when N = 1, there is only one possible full binary tree if N == 1: return [TreeNode(0)] # recursive case: # for each value of i from 1 to N-2 (inclusive), # we can form a full binary tree by creating a root node with value i, # and attaching all possible full binary trees of size i-1 and N-i-1 to its left and right subtrees, respectively res = [] for i in range(1, N-1): for left in self.allPossibleFBT(i): for right in self.allPossibleFBT(N-i-1): root = TreeNode(i) root.left = left root.right = right res.append(root) return res

var allPossibleFBT = function(N) { if (N % 2 === 0) { return []; } if (N === 1) { return [new TreeNode(0)]; } let result = []; for (let i = 1; i < N; i += 2) { let left = allPossibleFBT(i); let right = allPossibleFBT(N - 1 - i); for (let l of left) { for (let r of right) { let root = new TreeNode(0); root.left = l; root.right = r; result.push(root); } } } return result; };

There are many possible solutions to this problem. One approach would be to use a recursive function to generate all possible full binary trees. The base case would be when the tree is empty, and the recursive case would be when the tree has two nodes. For each node in the tree, the function would generate all possible full binary trees with that node as the root. The function would then return a list of all the possible trees. Another approach would be to use a iterative function to generate all possible full binary trees. The function would start with an empty tree. For each node in the tree, the function would generate all possible full binary trees with that node as the root. The function would then return a list of all the possible trees.

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public IListAllPossibleFBT(int N) { // edge case if (N % 2 == 0) { return new List (); } List [] dp = new List [N + 1]; dp[1] = new List () { new TreeNode(0) }; for (int i = 3; i <= N; i += 2) { dp[i] = new List (); for (int j = 1; j < i - 1; j += 2) { foreach (TreeNode left in dp[j]) { foreach (TreeNode right in dp[i - j - 1]) { TreeNode root = new TreeNode(0); root.left = left; root.right = right; dp[i].Add(root); } } } } return dp[N]; } }