LeetCode 894 - All Possible Full Binary Trees

LeetCode Problem 894

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Tree, Recursion, Memoization, Binary Tree

Solution

Problem Understanding

The problem asks us to generate every possible full binary tree that contains exactly n nodes. A full binary tree is a special kind of binary tree where every node has either exactly two children or no children at all. In other words, a node can never have only one child.

The input is a single integer n, representing the total number of nodes that must appear in each generated tree. Every node in every tree must contain the value 0, so the actual node values are irrelevant. The only thing that matters is the structure of the trees.

The output is a list containing the root node of every distinct full binary tree that can be formed using exactly n nodes. Since the problem allows the trees to be returned in any order, we do not need to worry about sorting or deterministic ordering.

A very important observation comes from the definition of a full binary tree. Every time we add an internal node, it contributes exactly two children. Because of this property, a full binary tree always contains an odd number of nodes. That means if n is even, the answer must immediately be an empty list.

The constraint 1 <= n <= 20 is relatively small, which strongly suggests that generating all valid trees is feasible. However, the number of possible trees grows quickly, so recomputing the same subtree combinations repeatedly would be inefficient. This hints that memoization or dynamic programming will be important.

Several edge cases are important:

• If n is even, no full binary tree can exist.
• If n == 1, the only valid tree is a single node with no children.
• Recursive generation can repeatedly solve the same subproblems, causing exponential recomputation without memoization.
• Tree construction must avoid accidentally modifying shared subtree references after reuse.

Approaches

Brute Force Approach

A brute force solution would attempt to recursively construct every possible binary tree with n nodes and then filter out the trees that are not full binary trees.

For each node, we could try every possible split of the remaining nodes between the left and right subtrees. After generating all combinations, we would check whether every node satisfies the full binary tree property.

This approach is correct because it explores all possible structures exhaustively. However, it is extremely inefficient because:

• Many invalid trees are generated only to be discarded later.
• The same subtree sizes are recomputed repeatedly.
• Recursive branching grows explosively as n increases.

Even with n <= 20, naive recursion without memoization performs excessive redundant work.

Optimal Approach

The key insight is that full binary trees have a strict structural property:

• Every node either contributes zero children or exactly two children.
• Therefore, the left and right subtree sizes must both be odd.
• If the root consumes one node, the remaining n - 1 nodes must be split into two odd-sized groups.

This leads naturally to recursive construction:

• For every odd split of n - 1,
• Generate all possible left subtrees,
• Generate all possible right subtrees,
• Combine every left subtree with every right subtree.

Since the same subtree sizes appear repeatedly during recursion, memoization dramatically improves performance. Once we compute all full binary trees for a particular node count, we store and reuse the result.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential, much worse than necessary	Exponential	Generates many invalid trees and recomputes subproblems repeatedly
Optimal	O(Cn) where Cn is the number of generated trees	O(Cn)	Uses memoization and only constructs valid full binary trees

Algorithm Walkthrough

1. First, check whether n is even. A full binary tree always contains an odd number of nodes, so if n % 2 == 0, immediately return an empty list.
2. Create a memoization map where the key is the number of nodes and the value is the list of all possible full binary trees with that many nodes. This prevents recomputing the same subtree structures repeatedly.
3. Define a recursive function build(node_count) that returns all full binary trees containing exactly node_count nodes.
4. Inside the recursive function, first check whether the result already exists in the memoization map. If it does, return the cached list immediately.
5. Handle the base case. If node_count == 1, the only possible full binary tree is a single leaf node. Return a list containing one TreeNode(0).
6. For larger odd values of node_count, iterate through every possible odd-sized left subtree:

• The root consumes one node.
• The remaining node_count - 1 nodes must be divided between the left and right subtrees.
• Both subtree sizes must remain odd.

7. For each valid split:

• Recursively generate all left subtrees.
• Recursively generate all right subtrees.

8. Combine every left subtree with every right subtree:

• Create a new root node.
• Attach the chosen left subtree.
• Attach the chosen right subtree.
• Add the completed tree to the result list.

9. Store the completed result list in the memoization map before returning it.
10. Return the list of all generated trees.

Why it works

The algorithm works because every full binary tree can be uniquely decomposed into:

• One root node,
• One full left subtree,
• One full right subtree.

By recursively generating every valid odd-sized left and right subtree combination, we enumerate every possible full binary tree exactly once. Memoization guarantees that each subtree size is computed only once.

Python Solution

# 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

from typing import List, Optional

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        memo = {}

        def build(node_count: int) -> List[Optional[TreeNode]]:
            if node_count in memo:
                return memo[node_count]

            if node_count == 1:
                return [TreeNode(0)]

            trees = []

            for left_nodes in range(1, node_count, 2):
                right_nodes = node_count - 1 - left_nodes

                left_subtrees = build(left_nodes)
                right_subtrees = build(right_nodes)

                for left_tree in left_subtrees:
                    for right_tree in right_subtrees:
                        root = TreeNode(0)
                        root.left = left_tree
                        root.right = right_tree
                        trees.append(root)

            memo[node_count] = trees
            return trees

        if n % 2 == 0:
            return []

        return build(n)

The implementation starts by handling memoization with the memo dictionary. Each key stores all possible full binary trees for a specific node count.

The recursive helper function build() performs the actual tree generation. The base case occurs when only one node is needed, which produces a single leaf node.

The main recursive logic iterates through all odd-sized left subtree possibilities. Since the total node count must remain odd, both left and right subtree sizes must also be odd.

For every left subtree and right subtree combination, a new root node is created and connected to those subtrees. The completed tree is then appended to the result list.

Finally, memoization ensures that each subtree size is generated only once, which avoids exponential recomputation.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func allPossibleFBT(n int) []*TreeNode {
    if n%2 == 0 {
        return []*TreeNode{}
    }

    memo := make(map[int][]*TreeNode)

    var build func(int) []*TreeNode

    build = func(nodeCount int) []*TreeNode {
        if trees, exists := memo[nodeCount]; exists {
            return trees
        }

        if nodeCount == 1 {
            return []*TreeNode{
                &TreeNode{Val: 0},
            }
        }

        var trees []*TreeNode

        for leftNodes := 1; leftNodes < nodeCount; leftNodes += 2 {
            rightNodes := nodeCount - 1 - leftNodes

            leftSubtrees := build(leftNodes)
            rightSubtrees := build(rightNodes)

            for _, leftTree := range leftSubtrees {
                for _, rightTree := range rightSubtrees {
                    root := &TreeNode{
                        Val:   0,
                        Left:  leftTree,
                        Right: rightTree,
                    }

                    trees = append(trees, root)
                }
            }
        }

        memo[nodeCount] = trees
        return trees
    }

    return build(n)
}

The Go implementation follows the same recursive memoized strategy as the Python solution. The primary difference is the use of slices and pointers.

Go uses nil pointers for missing children, while Python uses None. The memoization map stores slices of *TreeNode.

Because Go requires explicit pointer allocation, each new node is created using &TreeNode{} syntax.

Integer overflow is not a concern because the constraint n <= 20 is very small.

Worked Examples

Example 1

Input:

n = 7

We begin with:

build(7)

The root uses one node, leaving:

6 nodes remaining

Possible odd splits are:

Left Nodes	Right Nodes
1	5
3	3
5	1

Split: Left = 1, Right = 5

build(1) returns:

[leaf]

Now compute build(5).

Possible splits inside build(5):

Left Nodes	Right Nodes
1	3
3	1

This produces two distinct trees for size 5.

Combining the one-node left subtree with the two possible right subtrees produces:

2 trees

Split: Left = 3, Right = 3

build(3) produces exactly one tree:

    0
   / \
  0   0

Combining the single left tree with the single right tree produces:

1 tree

Split: Left = 5, Right = 1

Symmetric to the first case.

This produces:

2 trees

Total:

Split	Trees Produced
1 + 5	2
3 + 3	1
5 + 1	2

Final answer:

5 total trees

Example 2

Input:

n = 3

We call:

build(3)

Possible split:

Left Nodes	Right Nodes
1	1

Both recursive calls return single leaf nodes.

Combining them gives:

    0
   / \
  0   0

Only one valid full binary tree exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(Cn)	We must generate every valid full binary tree
Space	O(Cn)	Memoization stores all generated trees

The exact number of full binary trees grows according to the Catalan-like structure of binary tree combinations. Since the output itself can become very large, the runtime is fundamentally bounded by the number of generated trees.

Memoization ensures that each subtree size is computed once, preventing redundant recursive work.

Test Cases

from collections import deque

def serialize(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

solution = Solution()

# Example case: n = 1
trees = solution.allPossibleFBT(1)
assert len(trees) == 1  # Single node tree

# Example case: n = 3
trees = solution.allPossibleFBT(3)
assert len(trees) == 1  # Only one valid full binary tree

# Example case: n = 7
trees = solution.allPossibleFBT(7)
assert len(trees) == 5  # Known result from problem statement

# Even number of nodes
trees = solution.allPossibleFBT(2)
assert trees == []  # Impossible for full binary trees

# Another even case
trees = solution.allPossibleFBT(10)
assert trees == []  # No valid trees

# Larger odd input
trees = solution.allPossibleFBT(9)
assert len(trees) == 14  # Known count for n = 9

# Verify all roots contain value 0
trees = solution.allPossibleFBT(5)
assert all(tree.val == 0 for tree in trees)  # All node values must be 0

# Verify every generated tree is full
def is_full(node):
    if not node:
        return True

    if (node.left is None) != (node.right is None):
        return False

    return is_full(node.left) and is_full(node.right)

trees = solution.allPossibleFBT(7)
assert all(is_full(tree) for tree in trees)  # Every tree must be full

Test	Why
n = 1	Validates base case
n = 3	Smallest non-trivial full binary tree
n = 7	Matches official example
n = 2	Ensures even inputs return empty
n = 10	Additional even-number validation
n = 9	Verifies larger recursive generation
Root value checks	Ensures all node values are zero
Full-tree validation	Confirms structural correctness

Edge Cases

One important edge case occurs when n is even. Full binary trees always contain an odd number of nodes because every internal node contributes exactly two children. A naive implementation might still attempt recursion for even values, wasting time or generating invalid structures. The implementation handles this immediately with an early return of an empty list.

Another important case is n == 1. This is the smallest valid full binary tree and serves as the recursive base case. Without this condition, recursion would never terminate correctly. The implementation returns a single leaf node wrapped in a list.

A subtler edge case involves repeated subtree computations. For example, while generating trees for n = 9, the algorithm repeatedly needs all trees of size 3, 5, and 7. Without memoization, these subproblems would be recomputed many times, causing severe performance degradation. The memoization dictionary ensures each subtree size is generated exactly once.

Another potential source of bugs is incorrect subtree splitting. If even subtree sizes were allowed during recursion, invalid non-full trees could be generated. The implementation avoids this by iterating only through odd subtree sizes using:

for left_nodes in range(1, node_count, 2):

This guarantees both subtrees always contain odd numbers of nodes, preserving the full binary tree property throughout recursion.