894. All Possible Full Binary Trees - Explanation

1. Recursion

Intuition

A full binary tree has every node with either 0 or 2 children. If we have n nodes, one becomes the root, and we split the remaining n-1 nodes between the left and right subtrees. Each subtree must also be a full binary tree.

We try all possible ways to distribute n-1 nodes between left and right. For each valid split, we recursively generate all possible left subtrees and all possible right subtrees, then combine each left-right pair under a new root.

Algorithm

Base cases: If n == 0, return an empty list. If n == 1, return a list with a single node.
For l from 0 to n-1:
- Set r = n - 1 - l (remaining nodes for the right subtree).
- Recursively get all full binary trees with l nodes for the left.
- Recursively get all full binary trees with r nodes for the right.
- For each combination of left and right subtree, create a new root and add it to the res.
Return the res list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        def backtrack(n):
            if n == 0:
                return []
            if n == 1:
                return [TreeNode(0)]

            res = []
            for l in range(n):
                r = n - 1 - l
                leftTrees, rightTrees = backtrack(l), backtrack(r)

                for t1 in leftTrees:
                    for t2 in rightTrees:
                        res.append(TreeNode(0, t1, t2))
            return res

        return backtrack(n)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n * 2 ^ n)$

2. Recursion (Optimal)

Intuition

A full binary tree with n nodes only exists when n is odd. Every full binary tree has one root plus pairs of nodes in the subtrees, so the total must be odd. This lets us prune impossible cases immediately.

Additionally, we only need to try odd values for the left subtree size since each subtree must also form a valid full binary tree (requiring an odd count). This cuts the search space roughly in half.

Algorithm

If n is even, return an empty list (impossible to form a full binary tree).
If n == 1, return a list with a single node.
For left from 1 to n-1, stepping by 2 (odd values only):
- Recursively get all full binary trees with left nodes.
- Recursively get all full binary trees with n - 1 - left nodes.
- Combine each pair under a new root and add to the res.
Return the res list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []
        if n == 1:
            return [TreeNode(0)]

        res = []
        for left in range(1, n, 2):
            leftSubTree = self.allPossibleFBT(left)
            rightSubTree = self.allPossibleFBT(n - 1 - left)
            for l in leftSubTree:
                for r in rightSubTree:
                    root = TreeNode(0, l, r)
                    res.append(root)
        return res

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n * 2 ^ n)$

3. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same subproblems multiple times. For example, when building trees of size 7, we compute trees of size 3 several times across different branches.

By caching results in a hash map or array, we ensure each subproblem is solved only once. The first time we compute all trees for a given n, we store them. Future calls simply return the cached dp result.

Algorithm

Create a memoization map dp to store results for each n.
Define a recursive function dfs(n):
- If n is even, return an empty list.
- If n == 1, return a list with a single node.
- If dp[n] exists, return it.
- For left from 1 to n-1, stepping by 2:
  - Recursively get left and right subtrees.
  - Combine all pairs under new roots.
- Store the res in dp[n] and return it.
Call dfs(n) and return the result.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        dp = {}

        def dfs(n):
            if n % 2 == 0:
                return []
            if n == 1:
                return [TreeNode(0)]
            if n in dp:
                return dp[n]

            res = []
            for left in range(1, n, 2):
                leftSubTree = dfs(left)
                rightSubTree = dfs(n - 1 - left)
                for l in leftSubTree:
                    for r in rightSubTree:
                        res.append(TreeNode(0, l, r))

            dp[n] = res
            return res

        return dfs(n)

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n * 2 ^ n)$

4. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursing from n down and caching, we can build solutions bottom-up. We start with the base case (n=1), then iteratively compute solutions for n=3, 5, 7, ... up to the target.

For each odd value, we combine previously computed smaller trees to form larger ones. Since we only ever need results for smaller odd numbers, and we compute them in order, all dependencies are satisfied when we need them.

Algorithm

If n is even, return an empty list.
Create an array dp where dp[i] will store all full binary trees with i nodes.
Initialize dp[1] with a single node.
For nodes from 3 to n, stepping by 2:
- For left from 1 to nodes-1, stepping by 2:
  - Set right = nodes - 1 - left.
  - For each tree in dp[left] and each tree in dp[right]:
    - Create a new root combining them and add to dp[nodes].
Return dp[n].

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0:
            return []

        dp = [[] for _ in range(n + 1)]
        dp[1] = [TreeNode(0)]

        for nodes in range(3, n + 1, 2):
            res = []
            for left in range(1, nodes, 2):
                right = nodes - 1 - left
                for t1 in dp[left]:
                    for t2 in dp[right]:
                        res.append(TreeNode(0, t1, t2))
            dp[nodes] = res

        return dp[n]

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n * 2 ^ n)$

Common Pitfalls

Forgetting That Full Binary Trees Require Odd Node Counts

A full binary tree can only exist when n is odd. Each node either has 0 or 2 children, so starting with 1 root and adding pairs means the total is always odd. Failing to check this leads to wasted computation or incorrect results.

# Wrong: missing the odd check
def allPossibleFBT(n):
    if n == 1:
        return [TreeNode(0)]
    # Will waste time on even n values

Reusing Tree Nodes Across Different Results

When combining left and right subtrees, you must create a new root node for each combination. Reusing the same node object causes all trees to share structure, corrupting the results.

# Wrong: reusing same root node
root = TreeNode(0)
for l in leftTrees:
    for r in rightTrees:
        root.left, root.right = l, r
        res.append(root)  # All entries point to same node!

Iterating Over Even Values for Subtree Sizes

In a full binary tree, both left and right subtrees must also be full binary trees, meaning they need odd node counts. Iterating over all values instead of only odd values wastes time and produces empty results for even sizes.

# Wrong: iterating all values
for left in range(1, n):  # Includes even values
    ...

# Correct: step by 2 to only use odd values
for left in range(1, n, 2):
    ...