Problem

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.

Examples

Example 1:

 graph TD
   %% Tree 1
   subgraph T1[Tree 1]
     A1[0] --> B1[0] & C1[0]
     C1[0] --> D1[0] & E1[0]
     E1[0] --> F1[0] & G1[0]
   end
 
   %% Tree 2
   subgraph T2[Tree 2]
     A2[0] --> B2[0] & C2[0]
     C2[0] --> D2[0] & E2[0]
     D2[0] --> F2[0] & G2[0]
   end
 
   %% Tree 3
   subgraph T3[Tree 3]
     A3[0] --> B3[0] & C3[0]
     B3[0] --> D3[0] & E3[0]
     C3[0] --> F3[0] & G3[0]
   end
  
graph TD;
   %% Tree 4
   subgraph T4[Tree 4]
     A4[0] --> B4[0] & C4[0]
     B4[0] --> D4[0] & E4[0]
     E4[0] --> F4[0] & G4[0]
   end
 
   %% Tree 5
   subgraph T5[Tree 5]
     A5[0] --> B5[0] & C5[0]
     B5[0] --> D5[0] & E5[0]
     D5[0] --> F5[0] & G5[0]
   end
  
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]]

Solution

Method 1 - Recursion

  1. Base Case and Initial Check:
    • A full binary tree cannot have an even number of nodes. This is because a full binary tree either has 0 or 2 children for every node. Hence, for any given n that is even, it is impossible to create such a tree. For example, with n = 2 nodes, you cannot form a valid tree since one node would be left without a pair.
    • If n is even, we return an empty list as there are no possible full binary trees.
  2. Recursive Build and Memoization:
    • For an odd number n, we compute possible full binary trees by recursively finding potential subtrees at each level.
    • For every i (where i is the number of nodes in the left subtree), we compute allPossibleFBT(i) for the left subtree and allPossibleFBT(n - 1 - i) for the right subtree (considering the root makes one node).
    • Combining all possible left and right subtrees forms the full binary trees for the current node count n.
    • Memoization is employed to store results for each computed i to avoid recomputation and enhance efficiency.

Code

Java
class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return new ArrayList<>();
        }
        return allPossibleFBTUtil(n, new HashMap<>());
    }

    private List<TreeNode> allPossibleFBTUtil(int n, Map<Integer, List<TreeNode>> memo) {
        if (n == 1) {
            return Arrays.asList(new TreeNode(0));
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        List<TreeNode> ans = new ArrayList<>();
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> leftTrees = allPossibleFBTUtil(i, memo);
            List<TreeNode> rightTrees = allPossibleFBTUtil(n - 1 - i, memo);
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    ans.add(root);
                }
            }
        }
        memo.put(n, ans);
        return ans;
    }
}
Python
class TreeNode:
    def __init__(self, x: int):
        self.val: int = x
        self.left: 'TreeNode' = None
        self.right: 'TreeNode' = None

class Solution:
    def allPossibleFBT(self, n: int) -> List[TreeNode]:
        if n % 2 == 0:
            return []
        return self._allPossibleFBT(n, {})
    
    def _allPossibleFBT(self, n: int, memo: Dict[int, List[TreeNode]]) -> List[TreeNode]:
        if n == 1:
            return [TreeNode(0)]
        if n in memo:
            return memo[n]
        ans: List[TreeNode] = []
        for i in range(1, n, 2):
            left_trees = self._allPossibleFBT(i, memo)
            right_trees = self._allPossibleFBT(n - 1 - i, memo)
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    ans.append(root)
        memo[n] = ans
        return ans

Complexity

  • ⏰ Time complexity: O(2^n), because each recursive call generates exponential subproblems.
  • 🧺 Space complexity: O(2^n) for storing all trees which also requires exponential space.