## DEV Community

Abhishek Chaudhary

Posted on

# 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`

SOLUTION:

``````# 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 getTrees(self, n: int) -> List[Optional[TreeNode]]:
trees = []
if n == 1:
return [TreeNode()]
if n in self.cache:
return self.cache[n]
for i in range(1, n, 2):
lefts = self.getTrees(i)
rights = self.getTrees(n - i - 1)
for left in lefts:
for right in rights:
root = TreeNode()
root.left = left
root.right = right
trees.append(root)
self.cache[n] = trees
return trees

def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
self.cache = {}
return self.getTrees(n)
``````