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 <= 20Problem Overview: You are given an odd integer n. Build and return every possible full binary tree with exactly n nodes. A full binary tree means every node has either 0 or 2 children. The result is a list of root nodes representing all valid structures.
Approach 1: Recursive Construction with Memoization (Time: ~O(n * F(n)), Space: ~O(n * F(n)))
The key observation: a full binary tree always contains an odd number of nodes. If the root uses one node, the remaining n-1 nodes must be split between the left and right subtrees, and both subtree sizes must also be odd. Recursively generate all left subtrees of size i and all right subtrees of size n-1-i, then attach each combination to a new root. This naturally forms a Cartesian product of left and right subtree possibilities.
Naive recursion recomputes the same subtree sizes many times. Add caching (memoization) keyed by n. When the function needs trees with k nodes, it first checks the cache and reuses previously generated lists. This drastically reduces recomputation and is the most common interview solution using recursion with memoization.
Approach 2: Dynamic Programming (Iterative Build) (Time: ~O(n * F(n)), Space: ~O(n * F(n)))
The recursive idea can be converted into bottom‑up dynamic programming. Maintain a DP array where dp[i] stores all full binary trees with i nodes. Start with the base case dp[1] containing a single node tree. Then iterate through odd sizes from 3 to n.
For each size i, try every odd split left and right = i - 1 - left. Combine each tree from dp[left] with each tree from dp[right] under a new root node. Append the constructed trees into dp[i]. This approach avoids recursion and makes the dependency structure explicit while still generating every valid binary tree configuration.
Recommended for interviews: Recursive generation with memoization is the expected approach. It directly models the recursive structure of full binary trees and demonstrates understanding of subtree decomposition and caching. Mention the odd-node constraint first, then describe splitting n-1 nodes across left and right subtrees. The iterative DP version shows deeper understanding but usually comes after explaining the recursive insight.
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 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.
Python
JavaScript
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.
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.
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.
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.
If n=1, return a list with a single node directly.
If n > 1, we can enumerate the number of nodes i in the left subtree, then the number of nodes in the right subtree is n-1-i. For each case, we recursively construct all possible genuine binary trees for the left and right subtrees. Then we combine the left and right subtrees in pairs to get all possible genuine binary trees.
This process can be optimized with memoization search to avoid repeated calculations.
The time complexity is O(\frac{2^n}{\sqrt{n}}), and the space complexity is O(\frac{2^n}{\sqrt{n}}). Where n is the number of nodes.
| Approach | Complexity |
|---|---|
| Recursive Approach with Caching | The time complexity is |
| Dynamic Iterative Approach | This method maintains a time complexity of |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | ~O(n * F(n)) | ~O(n * F(n)) | Most intuitive solution. Preferred in interviews when explaining recursive tree construction. |
| Dynamic Programming (Iterative) | ~O(n * F(n)) | ~O(n * F(n)) | When avoiding recursion or demonstrating bottom-up DP construction of tree structures. |
All Possible Full Binary Trees - Memoization - Leetcode 894 - Python • NeetCode • 40,638 views views
Watch 9 more video solutions →Practice All Possible Full Binary Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor