LeetCode 894: All Possible Full Binary Trees

Problem Restatement

We are given an integer n.

Return a list of all possible full binary trees with exactly n nodes.

A full binary tree is a binary tree where every node has either:

No node may have exactly one child.

Each node has value 0. We only care about the tree shapes.

LeetCode asks for all possible full binary trees with n nodes, and each node must have value 0.

Input and Output

Function shape:

def allPossibleFBT(self, n: int) -> list[Optional[TreeNode]]:
    ...

Examples

Example 1:

Input: n = 7
Output: all 5 full binary tree shapes with 7 nodes

There are five possible shapes.

One example shape is:

        0
      /   \
     0     0
    / \   / \
   0   0 0   0

Another valid shape is:

        0
      /   \
     0     0
          / \
         0   0
            / \
           0   0

Example 2:

Input: n = 3
Output: one tree

The only full binary tree with 3 nodes is:

  0
 / \
0   0

Example 3:

Input: n = 1
Output: one tree

A single node is a valid full binary tree because it has zero children.

First Thought: Build Trees Recursively

A full binary tree is naturally recursive.

For n > 1, the root must have:

1. A left full binary subtree.
2. A right full binary subtree.

The root uses one node.

So the left and right subtrees must use:

n - 1

nodes in total.

If the left subtree uses left_nodes, then the right subtree uses:

right_nodes = n - 1 - left_nodes

Both subtrees must themselves be full binary trees.

Key Insight

A full binary tree always has an odd number of nodes.

Reason:

Each internal node has exactly 2 children.

Let:

I = number of internal nodes
L = number of leaves

In a full binary tree:

L = I + 1

So total nodes are:

I + L = I + (I + 1) = 2I + 1

That is always odd.

Therefore, if n is even, the answer is empty.

For odd n, try every odd split of nodes between left and right subtrees.

Algorithm

Use recursion with memoization.

Define:

build(nodes)

to return all full binary trees with exactly nodes nodes.

Base cases:

1. If nodes is even, return an empty list.
2. If nodes == 1, return a single leaf node.

Recursive case:

For every odd left_nodes from 1 to nodes - 2:

right_nodes = nodes - 1 - left_nodes

Get all left trees:

left_trees = build(left_nodes)

Get all right trees:

right_trees = build(right_nodes)

For every pair (left, right), create a new root:

TreeNode(0, left, right)

Add it to the result.

Memoization prevents recomputing the same build(nodes) many times.

Walkthrough

Use:

n = 5

The root uses one node, so the two subtrees must use 4 nodes total.

Possible odd splits:

For split (1, 3):

Left subtree is a leaf.

Right subtree is the only full binary tree with 3 nodes.

Shape:

    0
   / \
  0   0
     / \
    0   0

For split (3, 1):

Left subtree has 3 nodes.

Right subtree is a leaf.

Shape:

    0
   / \
  0   0
 / \
0   0

So there are two full binary trees with 5 nodes.

Correctness

The algorithm returns only full binary trees.

For nodes == 1, it returns a leaf node, which is full because it has zero children.

For nodes > 1, every created tree has a root with exactly two children. Each child is produced by a recursive call that returns only full binary trees. Therefore, every node in the final tree has either zero or two children.

The algorithm returns only trees with exactly nodes nodes.

Each constructed tree uses one root, left_nodes nodes in the left subtree, and right_nodes nodes in the right subtree. Since right_nodes = nodes - 1 - left_nodes, the total is exactly nodes.

The algorithm returns all possible full binary trees.

Take any full binary tree with nodes > 1. Its root has two children. Let the left subtree contain left_nodes nodes and the right subtree contain right_nodes nodes. Both are full binary trees, and:

left_nodes + right_nodes = nodes - 1

The algorithm tries this exact split. By induction, the recursive calls generate the exact left and right subtree shapes. Therefore, the algorithm constructs this tree.

Thus, the algorithm returns exactly all full binary trees with n nodes.

Complexity

The number of returned trees grows according to Catalan numbers.

Let:

T(n) = number of full binary trees with n nodes

The exact output size is already large, so the algorithm is output-sensitive.

Implementation

from functools import lru_cache
from typing import Optional

# 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]]:
        @lru_cache(None)
        def build(nodes: int) -> tuple[Optional[TreeNode], ...]:
            if nodes % 2 == 0:
                return tuple()

            if nodes == 1:
                return (TreeNode(0),)

            result = []

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

                for left in build(left_nodes):
                    for right in build(right_nodes):
                        root = TreeNode(0)
                        root.left = left
                        root.right = right
                        result.append(root)

            return tuple(result)

        return list(build(n))

Code Explanation

We use lru_cache to memoize recursive results:

@lru_cache(None)
def build(nodes: int) -> tuple[Optional[TreeNode], ...]:

The function returns a tuple because cached values must be safe to reuse.

If nodes is even, no full binary tree can exist:

if nodes % 2 == 0:
    return tuple()

The base case is a single leaf:

if nodes == 1:
    return (TreeNode(0),)

For larger odd nodes, we try all odd left subtree sizes:

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

The right subtree size is determined by the remaining nodes:

right_nodes = nodes - 1 - left_nodes

For every left tree and right tree, create a new root:

root = TreeNode(0)
root.left = left
root.right = right

Finally, convert the cached tuple to a list:

return list(build(n))

Note on Shared Subtrees

With memoization, different returned trees may reuse the same subtree objects internally.

This is accepted on LeetCode because the judge treats the returned trees structurally.

For standalone code where callers may mutate returned trees, clone left and right subtrees before attaching them to a new root.

Testing

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

def count_nodes(root):
    if not root:
        return 0

    return 1 + count_nodes(root.left) + count_nodes(root.right)

def is_full(root):
    if not root:
        return True

    if root.left is None and root.right is None:
        return True

    if root.left is not None and root.right is not None:
        return is_full(root.left) and is_full(root.right)

    return False

def run_tests():
    s = Solution()

    assert len(s.allPossibleFBT(1)) == 1
    assert len(s.allPossibleFBT(2)) == 0
    assert len(s.allPossibleFBT(3)) == 1
    assert len(s.allPossibleFBT(5)) == 2
    assert len(s.allPossibleFBT(7)) == 5

    for tree in s.allPossibleFBT(7):
        assert count_nodes(tree) == 7
        assert is_full(tree)

    print("all tests passed")

run_tests()

Test meaning: