All Possible Full Binary Trees
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive definition of a full binary tree into a function. A full binary tree with n nodes is formed by a root, a left full binary subtree, and a right full binary subtree. The total number of nodes n must be odd. If n=1, it's a single node. For n > 1, we can partition the remaining n-1 nodes into a left subtree with i nodes and a right subtree with n-1-i nodes. Since both subtrees must also be full binary trees, i and n-1-i must be odd. We can iterate through all possible odd values for i, recursively generate all possible left and right subtrees, and combine them.
Algorithm
- The function
allPossibleFBT(n)is defined to return a list of all full binary trees withnnodes. - Base Case 1: If
nis an even number, it's impossible to form a full binary tree. Return an empty list. - Base Case 2: If
nis 1, the only possible tree is a single node. Return a list containing just this node. - Recursive Step: For an odd
n > 1, iterate through all possible odd numbers for the left subtree's node count, let's call iti, from1ton-2. - For each
i, the right subtree must havej = n - 1 - inodes. - Recursively call
allPossibleFBT(i)to get all possible left subtrees. - Recursively call
allPossibleFBT(j)to get all possible right subtrees. - Create a new tree for every combination of a left subtree and a right subtree. A new root node is created, and its
leftandrightchildren are set to the pair of subtrees. - Add each newly formed tree to a result list.
- Return the final list of trees.
Walkthrough
The core idea is to break down the problem of finding trees with n nodes into smaller subproblems. We observe the inherent recursive structure: any full binary tree with more than one node has a root, a left subtree, and a right subtree, both of which must also be full binary trees. This leads to a straightforward recursive algorithm.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<TreeNode> allPossibleFBT(int n) { List<TreeNode> result = new ArrayList<>(); // A full binary tree must have an odd number of nodes. if (n % 2 == 0) { return result; } // Base case: a tree with 1 node is just a single node. if (n == 1) { result.add(new TreeNode(0)); return result; } // Iterate through all possible numbers of nodes for the left subtree. // The number of nodes in a subtree must also be odd. for (int i = 1; i < n; i += 2) { int j = n - 1 - i; // Remaining nodes for the right subtree. List<TreeNode> leftSubtrees = allPossibleFBT(i); List<TreeNode> rightSubtrees = allPossibleFBT(j); // Combine every possible left subtree with every possible right subtree. for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root = new TreeNode(0); root.left = left; root.right = right; result.add(root); } } } return result; }}Complexity
Time
O(2^n). This is a loose upper bound. The function is called for the same `n` multiple times, leading to an exponential number of calls. For example, `allPossibleFBT(7)` calls `allPossibleFBT(5)` and `allPossibleFBT(3)` multiple times through different call paths. This repeated computation makes the algorithm very slow.
Space
O(n * 2^n). The space is required for the recursion call stack and to store the generated trees. The number of trees and their total nodes grows exponentially.
Trade-offs
Pros
Simple to understand and implement as it directly follows the mathematical definition.
Cons
Extremely inefficient due to a massive number of redundant computations.
The time complexity is exponential, making it infeasible for even moderately larger values of
n(though it might pass for the given constraints, it's a poor approach).Can lead to a
StackOverflowErrorfor largerndue to deep recursion, although not an issue forn <= 20.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private List < TreeNode >[] f ; public IList < TreeNode > AllPossibleFBT ( int n ) { f = new List < TreeNode >[ n + 1 ]; return Dfs ( n ); } private IList < TreeNode > Dfs ( int n ) { if ( f [ n ] != null ) { return f [ n ]; } if ( n == 1 ) { return new List < TreeNode > { new TreeNode () }; } List < TreeNode > ans = new List < TreeNode >(); for ( int i = 0 ; i < n - 1 ; ++ i ) { int j = n - 1 - i ; foreach ( var left in Dfs ( i )) { foreach ( var right in Dfs ( j )) { ans . Add ( new TreeNode ( 0 , left , right )); } } } f [ n ] = ans ; return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.