All Possible Full Binary Trees: Recursive Construction with Memoization

May 24, 20265 min read

leetcodeproblemmediumtreesdynamic-programming

Given an integer n, return a list of all possible full binary trees with n nodes. A full binary tree is one where every node has either 0 or 2 children. This is LeetCode 894: All Possible Full Binary Trees.

The first thing to notice is that full binary trees can only exist when n is odd. Every internal node contributes exactly 2 children, so starting from a single root, you always add nodes in pairs. If n is even, there is no valid full binary tree, and you return an empty list.

For n = 7, there are exactly 5 structurally unique full binary trees:

All 5 structurally unique full binary trees with 7 nodes. Root nodes are highlighted in blue, leaves in green.

The problem

You need to construct and return every structurally unique full binary tree with exactly n nodes. Each node in the output tree should have val = 0. The order of the trees in the result does not matter.

A full binary tree has a simple recursive structure: the root always has two children, and each child is itself the root of a full binary tree. This means you can break the problem down by choosing how many nodes go to the left subtree and how many go to the right.

The approach

The key insight is that after you place one node as the root, you have n - 1 nodes left to distribute between the left and right subtrees. Both subtrees must themselves be full binary trees, which means both must have an odd number of nodes. So you iterate over all ways to split n - 1 nodes into two odd groups: left gets i nodes and right gets n - 1 - i nodes, where i ranges over 1, 3, 5, and so on.

For each split, you recursively generate all possible full binary trees for the left side and all possible full binary trees for the right side. Then you take the Cartesian product: pair every left tree with every right tree, and attach each pair to a new root node. This gives you all full binary trees for that particular split.

Since the same subproblem (the same value of n) can appear multiple times across different recursive branches, you memoize the results. Once you have computed all full binary trees for a given n, you store them and return the cached list on future calls.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def allPossibleFBT(n):
    memo = {}

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

        result = []
        for i in range(1, n, 2):
            left_trees = build(i)
            right_trees = build(n - 1 - i)
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(0, left, right)
                    result.append(root)

        memo[n] = result
        return result

    return build(n)

Drill recursive tree construction with spaced repetition

Step-by-step walkthrough

Here is how the algorithm builds full binary trees from the ground up. Each step shows a piece of the recursive logic.

Step 1: Base case (n = 1)

A single node with no children is the only full binary tree with 1 node. This is your recursion's stopping point.

Step 2: Even n returns empty (n must be odd)

A full binary tree always has an odd number of nodes. Every internal node adds 2 children, so starting from 1 you only reach odd totals. If n is even, return an empty list immediately.

Step 3: Split n into left + right + 1 (root)

For each odd split where left = i and right = n - 1 - i (both positive odd numbers), recursively build all full binary trees for the left subtree and the right subtree.

Step 4: Cartesian product of left and right subtrees

For each split, take every combination of one left subtree and one right subtree. Attach them to a new root node. This produces all full binary trees for that particular split.

Step 5: Example trace for n = 5

n=5 splits into (left=1, right=3) and (left=3, right=1). Each gives 1*1 = 1 tree, for a total of 2 full binary trees.

Step 6: Memoize to avoid repeated work

The same value of n appears in multiple recursive branches. Cache the result for each n so you build each set of trees only once. This turns exponential repeated work into a single computation per unique n.

The recursion bottoms out at n = 1 (a single leaf node), then builds up from there. For n = 3, there is exactly one tree: a root with two leaf children. For n = 5, there are two trees. For n = 7, the five trees come from combining smaller subtrees across three different splits.

Complexity analysis

Metric	Value
Time	O(2^(n/2))
Space	O(n * 2^(n/2))

Time: The number of full binary trees with n nodes is the Catalan number C((n-1)/2), which grows as O(2^(n/2) / n^(3/2)). For each tree, you do O(n) work to construct it. The total is bounded by O(n * C((n-1)/2)), which is roughly O(2^(n/2)).

Space: You store all C((n-1)/2) trees in the memoization cache, each with n nodes. The memo also stores subtrees for smaller values of n. The total space is dominated by the output size.

Practice tree enumeration problems

The building blocks

Recursive tree construction

The pattern of choosing a root, recursively building all valid left subtrees and all valid right subtrees, then combining them with a Cartesian product is the same skeleton you see in Unique Binary Search Trees II. The only difference is the constraint: here you need full binary trees (every node has 0 or 2 children), while in BST generation you need valid BST ordering. The recursive decomposition is identical.

Memoization over structure counts

Because the problem only depends on the count of nodes (not their values or positions), the subproblem space is small. There are at most n/2 unique odd values from 1 to n, so the memo table has at most n/2 entries. This is similar to how Climbing Stairs memoizes over step counts, but here each memo entry stores a list of tree objects rather than a single number.

Edge cases

n = 1: Return a list with a single leaf node. This is the base case of the recursion.
Even n: Return an empty list. A full binary tree cannot have an even number of nodes.
n = 3: Return a list with one tree: a root node with two leaf children. This is the smallest non-trivial full binary tree.
Large n (n = 19 or 20): The constraint on LeetCode is 1 to 20. For n = 19, there are 1430 full binary trees. For n = 20, the answer is an empty list since 20 is even.

From understanding to recall

You now see how the recursive splitting works: reserve one node for the root, distribute the remaining n - 1 nodes into two odd-sized groups, recursively build all trees for each group, and combine with the Cartesian product. Memoization ensures you never rebuild the same set of trees twice.

But will you remember all of this under interview pressure? Will you remember that n must be odd? Will you remember to iterate i in steps of 2 so both sides stay odd? Will you write the nested loop that pairs every left subtree with every right subtree without hesitating?

Spaced repetition closes the gap between understanding and recall. You write the build function from scratch at increasing intervals. After a few rounds, the base case, the odd-only loop, the Cartesian product, and the memoization are all automatic. When a tree enumeration problem appears in your interview, you reach for this pattern without thinking.

Build lasting recall with CodeBricks

Unique Binary Search Trees II - Same recursive construction pattern but with BST ordering constraints instead of full binary tree constraints
Unique Binary Search Trees - Counting the number of structurally unique BSTs rather than constructing them, using the Catalan number relationship
Generate Parentheses - Another problem where you enumerate all valid structures by making constrained recursive choices at each step