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 <= 20In #894 All Possible Full Binary Trees, the goal is to generate every full binary tree containing n nodes. A key observation is that a full binary tree requires every node to have either 0 or 2 children, which means the total number of nodes must be odd. If n is even, no valid tree can exist.
The typical strategy uses recursion combined with memoization. For a given n, treat one node as the root and distribute the remaining n-1 nodes between the left and right subtrees. Both subtrees must also contain an odd number of nodes. Recursively generate all valid left and right subtree combinations and attach them to the root.
Because many subtree sizes repeat during recursion, memoization (dynamic programming) is used to cache results for previously computed node counts. This avoids redundant computation and significantly improves performance. The number of generated trees grows rapidly (similar to Catalan growth), so complexity depends on the number of valid tree structures produced.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursion with Memoization | O(N * F(N)) where F(N) is the number of valid full binary trees | O(N * F(N)) for memo storage and recursion |
Inside code
This approach uses recursion to build all possible full binary trees for a given number of nodes. Since the problem exhibits overlapping subproblems, we can optimize the solution using memoization to store the results of previously solved subproblems. This significantly reduces the number of calculations needed.
The time complexity is O(2^N) due to the recursive generation of all possible subtrees. However, memoization helps to reduce the number of redundant calculations. The space complexity is also O(2^N) due to the storage of previously computed subtrees in the memo dictionary.
1class TreeNode {
2 constructor(val = 0, left = null, right = null) {
3 this.val = val;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9const memo = {};
10
11function allPossibleFBT(N) {
12 if (N % 2 === 0) return [];
13 if (N === 1) return [new TreeNode(0)];
14 if (memo[N]) return memo[N];
15
16 const result = [];
17 for (let left = 1; left < N; left += 2) {
18 for (let leftNode of allPossibleFBT(left)) {
19 for (let rightNode of allPossibleFBT(N - 1 - left)) {
20 const root = new TreeNode(0);
21 root.left = leftNode;
22 root.right = rightNode;
23 result.push(root);
24 }
25 }
26 }
27 memo[N] = result;
28 return result;
29}The JavaScript function allPossibleFBT implements a similar memoized recursive approach as the Python version. It creates instances of TreeNode for the roots of subtrees, and memoizes results to avoid redundant calculations for the same N. This helps in creating and efficiently storing valid trees.
This approach uses dynamic programming through an iterative method to build trees from the bottom up. We generate trees with increasingly larger numbers of nodes by combining smaller full binary trees, ensuring that each construction step builds on the last.
This method maintains a time complexity of O(2^N) and a space complexity of O(2^N) due to stored references of constructed trees. While iterative, it effectively mirrors the recursive/memoized strategies through explicit storage of previous calculations.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A full binary tree requires every node to have either zero or two children. Adding children always increases the node count by two, so the total number of nodes in a valid full binary tree must always be odd.
Yes, variations of tree generation and recursion problems like this appear in technical interviews at large tech companies. Interviewers often focus on recognizing structural properties, recursive decomposition, and optimizing with memoization.
A hash map or dictionary is commonly used for memoization, mapping a node count to all possible tree structures with that count. The results themselves are stored as lists of binary tree root nodes.
The optimal approach uses recursion with memoization. For each odd value of n, treat one node as the root and split the remaining nodes between left and right subtrees in all valid odd combinations. Memoizing results for each subtree size avoids recomputation and significantly improves efficiency.
In this Java solution, an array of lists dp is used to store trees. Each tree is represented by a TreeNode with zero value. This iterative process combines smaller trees at each step to build bigger trees, ensuring that all trees have the characteristic of full binary trees, which inherently coordinates the nodes' distribution between left and right subtrees.