# 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:

| Children count | Meaning |
|---:|---|
| 0 | Leaf node |
| 2 | Internal node |

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

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | List of roots of all full binary trees with `n` nodes |
| Node value | Always `0` |
| Full binary tree rule | Every node has 0 or 2 children |

Function shape:

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

## Examples

Example 1:

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

There are five possible shapes.

One example shape is:

```text
        0
      /   \
     0     0
    / \   / \
   0   0 0   0
```

Another valid shape is:

```text
        0
      /   \
     0     0
          / \
         0   0
            / \
           0   0
```

Example 2:

```text
Input: n = 3
Output: one tree
```

The only full binary tree with 3 nodes is:

```text
  0
 / \
0   0
```

Example 3:

```text
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:

```text
n - 1
```

nodes in total.

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

```text
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:

```text
I = number of internal nodes
L = number of leaves
```

In a full binary tree:

```text
L = I + 1
```

So total nodes are:

```text
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:

```python
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`:

```python
right_nodes = nodes - 1 - left_nodes
```

Get all left trees:

```python
left_trees = build(left_nodes)
```

Get all right trees:

```python
right_trees = build(right_nodes)
```

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

```python
TreeNode(0, left, right)
```

Add it to the result.

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

## Walkthrough

Use:

```text
n = 5
```

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

Possible odd splits:

| Left nodes | Right nodes |
|---:|---:|
| 1 | 3 |
| 3 | 1 |

For split `(1, 3)`:

Left subtree is a leaf.

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

Shape:

```text
    0
   / \
  0   0
     / \
    0   0
```

For split `(3, 1)`:

Left subtree has 3 nodes.

Right subtree is a leaf.

Shape:

```text
    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:

```text
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(T(n) * n)` | We must create and return every tree, each with up to `n` nodes |
| Space | `O(T(n) * n)` | The output and memoized trees dominate |

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

## Implementation

```python
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:

```python
@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:

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

The base case is a single leaf:

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

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

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

The right subtree size is determined by the remaining nodes:

```python
right_nodes = nodes - 1 - left_nodes
```

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

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

Finally, convert the cached tuple to a list:

```python
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

```python
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:

| Test | Why |
|---|---|
| `n = 1` | Single leaf tree |
| `n = 2` | Even node count cannot form a full binary tree |
| `n = 3` | One root with two leaves |
| `n = 5` | Two possible shapes |
| `n = 7` | Five possible shapes |
| Structural validation | Confirms node count and full-tree property |