The O(n) Club: All Possible Full Binary Trees

The O(n) Club: All Possible Full Binary Trees — Recursion Without Regrets

⚡ TL;DR

Want every structurally unique full binary tree for an odd number n? Just recurse your heart out: split the remaining nodes after the root into every odd pair, join all subtree combinations, and — please — memoize! Don’t even look at even n, unless you hate joy.
Here’s the totally unoptimized Java for masochists:

🧠 How Devs Usually Mess This Up

Classic rookie moves: Trying even n (nope), confusing ‘full’ with ‘complete’ or ‘perfect’ (nope), or thinking nodes’ values could possibly matter (shocker: they don’t). Pro tip: If you’re not memoizing, you’re just mining Bitcoin for the heating bill — this grows fast. Seriously.

🔍 What’s Actually Going On

Each root gets exactly two subtrees (unless it’s solo) — exactly like handing out two cupcakes to every guest, until nobody’s left standing but solitary crumbs. For every possible split (odd numbers only!), recursively build left/right trees, mash them together under a new root. Oh, and write down trees you’ve already built, unless you want infinite recursion to become your legacy.

🛠️ PseudoCode

Store & return:

memo[n] = result;
return result;

Memoized? Good. Ship it.

Get all combos: For each possible left and right subtree, combine:

for each left : leftTrees
 for each right : rightTrees
   root = TreeNode(0)
   root.left = left
   root.right = right
   result.add(root)

It’s tree buffet time. Take every combo.

Recursion on odd splits: For odd left/right sizes…

for (left = 1; left < n; left += 2)

There’s always a root node in the middle — leave room for two legit children.

Memoization: If you already solved for n, return the answer.

if (memo contains n) return memo[n];

Save your sanity, and RAM.

Base case: If n == 1, return a single-node tree.

if (n == 1) return [TreeNode(0)];

Single node? Congrats, it’s a tree.

💻 The Code

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 class Solution {
    Map<integer list>> memo = new HashMap<>();
    public List
<treenode> allPossibleFBT(int n) {
        if (n % 2 == 0) return List.of(); // No full binary for even n
        if (n == 1) return List.of(new TreeNode(0));
        if (memo.containsKey(n)) return memo.get(n);
        List
<treenode> out = new ArrayList<>();
        for (int left = 1; left < n; left += 2) {
            int right = n - 1 - left;
            for (TreeNode l : allPossibleFBT(left)) {
                for (TreeNode r : allPossibleFBT(right)) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    out.add(root);
                }
            }
        }
        memo.put(n, out);
        return out;
    }
}
</treenode></treenode></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

Even n? Instantly returns nothing. Full = always odd. No fudge room.
Tree shapes matter, not node values. They’re all zero, so structure is king.
Memoize, or cry endlessly. Naive recursion goes boom for big n.
‘Full’ ≠ ‘Complete’ ≠ ‘Perfect’: Interviewers *love* to trip you up here.
Complexity: Exponential trees, exponential RAM used. But with memoization, you’ll actually see some answers before Haskell is cool again.