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.
1from typing import List
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9memo = {}
10
11def allPossibleFBT(N: int) -> List[TreeNode]:
12 if N % 2 == 0:
13 return []
14 if N == 1:
15 return [TreeNode(0)]
16 if N in memo:
17 return memo[N]
18
19 result = []
20 for left in range(1, N, 2):
21 for left_subtree in allPossibleFBT(left):
22 for right_subtree in allPossibleFBT(N - 1 - left):
23 root = TreeNode(0)
24 root.left = left_subtree
25 root.right = right_subtree
26 result.append(root)
27
28 memo[N] = result
29 return resultThe Python function allPossibleFBT uses recursion and memoization to find all full binary trees of size N. The base case is when N is 1, where there's only one full binary tree possible, which consists of a single node. We recursively solve for every odd N, considering each odd number left as a candidate for the number of nodes in the left subtree and recursively constructing left and right subtrees. Every tree is combined with a new root node, creating a list of solutions that is cached in memo for future reference.
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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
vector<TreeNode*> allPossibleFBT(int N) {
vector<vector<TreeNode*>> dp(N + 1);
if (N % 2 == 0) return {};
dp[1] = {new TreeNode(0)};
for (int n = 3; n <= N; n += 2) {
vector<TreeNode*> result;
for (int left = 1; left < n; left += 2) {
for (auto* leftTree : dp[left]) {
for (auto* rightTree : dp[n - left - 1]) {
TreeNode* root = new TreeNode(0);
root->left = leftTree;
root->right = rightTree;
result.push_back(root);
}
}
}
dp[n] = result;
}
return dp[N];
}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.
The C++ solution utilizes a dynamic programming array dp where each entry dp[i] holds all the full binary trees possible with i nodes. Starting from the simplest case with one node, we iteratively combine smaller trees to build larger trees while ensuring balanced distribution between left and right subtrees, thereby leveraging previously computed solutions to optimize for new tree constructions.