## Similar Problems

Similar Problems not available

# All Possible Full Binary Trees - Leetcode Solution

## Companies:

LeetCode: All Possible Full Binary Trees Leetcode Solution

Difficulty: Medium

Topics: dynamic-programming tree binary-tree

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.

## All Possible Full Binary Trees Solution Code

`1`