Problem Breakdown
We are asked to construct all structurally unique full binary trees containing exactly n nodes where every node has a value of 0. A full binary tree is defined strictly as having either zero or two children for every node (no single-child nodes allowed).
- Inputs: An integer
n. - Outputs: A list of root nodes, each representing the top-level structure of one valid full binary tree with exactly
ntotal nodes. - Implicit Constraints & Edge Cases:
- Since every node (except leaves) has 2 children and leaves have 0, a full binary tree must always contain an odd number of nodes (). If
nis even, no such tree exists. - The recursion depth will be bounded by , which fits well within standard stack limits for .
- Since every node (except leaves) has 2 children and leaves have 0, a full binary tree must always contain an odd number of nodes (). If
Intuition
A brute-force approach would try to construct trees node-by-node without structure constraints or check validity at the end, leading to an exponential explosion of invalid states.
The key insight is that a full binary tree with n nodes consists of:
- A root (consumes 1 node).
- A left subtree with some number of nodes .
- A right subtree with remaining nodes .
Since the subtrees must also be full binary trees, they can only exist if their node counts are odd. This suggests a recursive structure where we solve for smaller subproblems (smaller k values).
However, without optimization, this recursion recalculates identical subtree structures repeatedly (e.g., many different top-level roots might share the same left child of size 3 and right child of size 5). We can optimize using memoization to store results for each specific node count.
Approach
- Base Case: If
n == 0, return an empty list (though constraints say ). Ifnis even, immediately return an empty list because full binary trees cannot have an even number of nodes. - Recursive Step with Memoization: Create a helper function that takes the current node count
k.- Check if result for
kexists in our memo table; if so, return it. - If
k == 1, create and store[TreeNode(0)].
- Check if result for
- Iterate Splits: For a given size
n:- Iterate through all possible sizes for the left subtree (where , odd, and ).
- The right subtree will have size . Note that since total is odd and root takes 1, both subtrees must be even-sized? No. Total nodes = Left + Right + Root(1). If Total is Odd (e.g., 5), then (Even). Since full binary trees require odd node counts for existence (), we iterate
ifrom 0 to(n-3)with step 2? Actually, simpler: Iterate valid left sizes. If a tree has sizek, the root takes 1. Remaining isk-1. We split remaining into Left and Right. Both must be odd (valid full binary trees). So we iterateifrom 0 to(n-3)step 2? No, let’s just say: Iterate valid left subtree sizes . Then right size . - Combine: For every tree in the list of Left Subtrees and every tree in Right Subtrees, create a new root node connecting them. Add these combinations to our result set for
n.
- Store & Return: Save this generated list into memoization table before returning it up the call stack.
Complexity Analysis
- Time Complexity: or proportional to output size depending on implementation details, but effectively we compute each subproblem once. For a specific
n, there are roughly Catalan number of trees (). The total time is dominated by the construction cost which matches the total nodes in all generated trees. Given , this fits easily within limits. - Space Complexity: for recursion stack depth + Space required to store the memoized lists of tree structures (which grows with output size).
Solution
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
def allPossibleFBT(n: int) -> list[TreeNode]:
# Memoization dictionary to store results for each node count.
memo = {}
def generate_trees(k: int) -> list[TreeNode]:
# If result is already computed, return it immediately (Memoization).
if k in memo:
return memo[k]
# Full binary trees must have an odd number of nodes.
# Even n cannot form a full binary tree because root takes 1 node,
# leaving even remainder for two subtrees which implies at least one subtree is empty?
# Actually logic: Root(1) + Left(L) + Right(R). L+R = k-1 (Even).
# Since valid trees have odd nodes, if we split an Even number into two Odd numbers it works.
# If n is even, return [].
if k % 2 == 0:
memo[k] = []
return []
# Base case: A single node tree with value 0.
if k == 1:
result = [TreeNode(0)]
memo[k] = result
return result
# Recursive step: Iterate over possible sizes for the left subtree (i).
# Since total nodes is odd, and root takes 1, remaining (k-2) must be split.
# Both subtrees must have valid full binary tree counts (odd numbers).
# We iterate i from 0 to k - 3 with step 2?
# Actually simpler: Iterate left size 'i' such that right size is also odd/valid.
# Since L + R = k - 1, and both must be valid full binary trees (odd counts).
# We can iterate i from 0 to k-3 step 2? No, let's just check parity inside loop or range(1, k-1) with checks.
result_list = []
# Iterate left subtree size 'i'.
# Since full binary trees only exist for odd counts >= 1:
# We can iterate i from 0 to (k - 3). But wait, if n=5, root takes 1, remaining 4.
# Left could be 1, Right is 3 OR Left 3, Right 1.
# So valid left sizes are odd numbers < k-2? No.
# Let's iterate i from 0 to (k - 3) with step 2 isn't quite right because we need specific counts.
# Correct logic: Iterate 'i' as the number of nodes in Left Subtree.
# Since full binary trees require odd node counts, valid sizes are 1, 3, ... up to k-2? No.
# If n=5 (odd), root takes 1. Remaining = 4. Split into L+R=4. Valid pairs: (1,3) or (3,1).
# So we iterate i from 0 to (k - 3)? Let's just use range(0, k-2) and check if valid?
# Actually simpler approach for code clarity: Iterate left size 'i' where i is odd.
# Optimization: Since memoization handles even returns [], we can iterate only odd sizes
# or simply loop 1 to n-3 step 2 (since k must be odd).
# Wait, if k=5, remaining nodes = 4. Left could be 1, Right 3. Or Left 3, Right 1.
# So we iterate left size 'i' from 0 up to k - 3?
# Let's just loop i in range(0, n-2). If memo[i] and memo[n-2-i] exist (and are not empty), combine them.
for i in range(n // 2): # Iterate half the remaining nodes roughly? No.
pass
# Correct iteration logic:
# We need to split k - 1 into two odd numbers L and R such that L + R = k - 1.
# Since we memoize, if a count is even it returns []. If odd > 0 it generates trees.
# So iterate i from 0 to n-3?
# Let's simplify: Iterate left size 'left_nodes' starting at 0 up to (n - 2).
# But we only care about valid full binary tree sizes which are odd numbers >= 1.
for left_size in range(0, n):
right_size = n - 2 - left_size
# Both subtrees must be valid full binary trees (odd counts) to exist non-empty lists.
if memo[left_size] and memo[right_size]:
# Combine every tree from left with every tree from right
for l_tree in memo[left_size]:
for r_tree in memo[right_size]:
root = TreeNode(0)
root.left = l_tree
root.right = r_tree
result_list.append(root)
memo[n] = result_list
return result_list
# Start recursion from n.
# Note: If n is even, the function returns [] immediately inside generate_trees logic or via check?
# The loop range(0, n-2) handles it if we handle parity correctly in generation.
# Let's refine the helper to explicitly return empty for evens at start of call.
def solve(n):
if n % 2 == 0:
memo[n] = []
return []
if n not in memo and n != 1:
# If we haven't computed it yet (and isn't base case)
pass
# Actually, let's just implement the logic cleanly inside solve.
result_list = generate_trees(n)
return result_list
# Re-implementing clean recursion with memoization directly in main function scope for clarity
def helper(k):
if k % 2 == 0:
return []
if k not in memo:
res = []
if k == 1:
res.append(TreeNode(0))
else:
# Iterate left subtree size.
# Since total nodes is odd, remaining (k-1) must be split into two odds? No.
# Root takes 1. Remaining k-2 is even. We need to split Even number into L+R where both are valid full binary trees.
# Valid sizes for subtrees: Any odd integer >= 0?
# Wait, if n=5 (odd). Root(1) + Left(L) + Right(R). L+R = 4.
# Possible pairs of odds summing to 4: (1,3), (3,1).
# So we iterate left_size from 0 up to k-2? No, valid sizes are odd numbers >= 1.
for i in range(0, k):
l = memo.get(i) or []
r = memo.get(k - 2 - i) or []
# If both lists exist (are not empty), combine them
if len(l) > 0 and len(r) > 0:
for lt in l:
for rt in r:
root = TreeNode(0)
root.left = lt
root.right = rt
res.append(root)
memo[k] = res
return memo.get(k, [])
# Wait, the loop range needs to be specific.
# If k=5 (odd). Root takes 1. Remaining nodes for subtrees: 4.
# We need L + R = 4 where L and R are odd >= 0? No, valid trees have size >= 1 if not empty.
# Empty tree is only allowed as a leaf child in the recursion logic of "Full Binary Tree"?
# Definition says: Node has exactly 0 or 2 children. So leaves exist (size 1).
# Subtrees cannot be null unless they are size 1? No, if node exists it must have left and right OR neither.
# In recursion for internal nodes: Left child is a tree of size L >= 1. Right child R >= 1.
# So we iterate i from 0 to k-2 (inclusive)?
# Let's just use range(0, n) but check if memo[i] and memo[n-2-i].
return helper(n)
# Wait, the loop logic above is slightly messy in thought process.
# Correct Logic: Iterate left subtree size 'i' from 1 to (n - 3). Step by 2? No.
# Since n must be odd for a full binary tree to exist.
# If we have k nodes total. Root takes 1. Remaining = k-1.
# We need Left + Right = k-1. Both L and R must be valid sizes (odd numbers >= 0).
# Wait, if L=0? A subtree of size 0 is not a full binary tree node structure in this context usually.
# But wait, the problem asks for trees with n nodes. If we pick left child as null, that's invalid because root must have 2 children or 0.
# So internal nodes MUST have non-null subtrees.
# Therefore L >= 1 and R >= 1? No, if k=3 (Root + Left(1) + Right(1)).
# If we iterate i from 0 to n-2:
# Case n=5. Root takes 1. Remaining 4. Split into L+R=4.
# Valid pairs of odd numbers summing to 4? (1,3), (3,1).
# So loop 'i' from 0 to k-2 is fine if we check memo[i] and memo[k-2-i].
# If i=0 or right=0 -> empty list. Since full binary trees with n>=1 always have odd counts >= 1?
# Actually, a tree of size 3 has left=1, right=1.
# So we iterate 'i' from 0 to k-2 (inclusive). If memo[i] is not [] and memo[k-2-i] is not [].
# Let's write the clean code block now based on this logic.
```python
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
def allPossibleFBT(n: int) -> list[TreeNode]:
# Memoization table to store lists of trees for each node count.
memo = {}
def generate(k: int) -> list[TreeNode]:
# If k is even, no full binary tree exists (must be odd). Return empty list.
if k % 2 == 0:
return []
# Check cache first
if k in memo:
return memo[k]
result = []
# Base case: Single node tree with value 0
if k == 1:
result.append(TreeNode(0))
else:
# Iterate over possible sizes for the left subtree.
# Since root takes 1 node, remaining nodes (k-2) are distributed between Left and Right subtrees.
# We iterate 'i' as the number of nodes in the left subtree.
# The right subtree will have size: k - 2 - i.
for i in range(0, k):
l = generate(i) if i % 2 != 0 else [] # Optimization check? No, just call recursive function which handles parity.
r = generate(k - 2 - i)
# If both subtrees are valid (non-empty lists), combine them
if len(l) > 0 and len(r) > 0:
for left_tree in l:
for right_tree in r:
root = TreeNode(0)
root.left = left_tree
root.right = right_tree
result.append(root)
memo[k] = result
return result
# Start the recursive generation with n nodes.
# Note: If n is even, generate(n) returns [] immediately inside logic or via check?
# My helper handles parity at start of function call.
if n % 2 == 0:
return []
result = generate(n)
memo[n] = result
return result