Given an integer n, return a list of all possible full binary trees with n nodes. Each node has value 0. A full binary tree is a tree where every node has either 0 or 2 children.

Examples

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],
         [0,0,0,null,null,0,0,0,0],
         [0,0,0,0,0,0,0],
         [0,0,0,0,0,null,null,null,null,0,0],
         [0,0,0,0,0,null,null,0,0]]
(5 distinct full binary trees)

Example 2:

Input: n = 3
Output: [[0,0,0]]
(Only one: root with two leaves)

Constraints

  • 1 <= n <= 20

Thinking Process

Key Observation

A full binary tree has the property: every internal node has exactly 2 children. This means:

  • n must be odd (each subtree adds 2 nodes at a time, plus the root)
  • If n is even, no full binary tree exists

Recursive Structure

A full binary tree with n nodes has:

  • 1 root node
  • i nodes in the left subtree
  • n - 1 - i nodes in the right subtree

where i is odd and ranges over 1, 3, 5, ..., n-2.

For each split, recursively generate all left trees and all right trees, then combine every pair.

Memoization

The same subproblem allPossibleFBT(k) may be called multiple times (e.g., both left and right subtrees can have the same size). Caching results avoids redundant computation.

Walk-through (n=5)

n=5: root + split remaining 4 nodes
  i=1: left=FBT(1)=[leaf], right=FBT(3)=[root+2leaves]
    → 1 tree
  i=3: left=FBT(3)=[root+2leaves], right=FBT(1)=[leaf]
    → 1 tree

Total: 2 full binary trees with 5 nodes
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

Input: n = 7
Output: [ list of all distinct full binary trees with 7 nodes ]

Solution Explanation

Approach: 1D DP (this problem)

Key idea: ### Key Observation

How the code works:

  • n must be odd (each subtree adds 2 nodes at a time, plus the root)
  • If n is even, no full binary tree exists
  • 1 root node
  • i nodes in the left subtree
  • n - 1 - i nodes in the right subtree

Walkthrough — input n = 7, expected output [[0,0,0,null,null,0,0,null,null,0,0],:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  • Not checking for even n (no full binary tree exists)
  • Stepping i by 1 instead of 2 (generates invalid subtree sizes)
  • Forgetting to create a new root for each (l, r) combination (sharing root nodes across trees corrupts the output)

Key Takeaways

  • “Generate all structurally unique trees” = recursive decomposition by subtree sizes + memoization
  • The odd-only constraint and step-by-2 iteration are specific to full binary trees
  • Same pattern as LC 95 (Unique BSTs II) – split, recurse, combine all pairs

References

Template Reference