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

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:

// Brute-force full binary trees (will roast CPUs for n > 9)
List
<treenode> allTrees(int n) {
    if (n == 1) return List.of(new TreeNode(0));
    List
<treenode> out = new ArrayList<>();
    for (int l = 1; l < n; l += 2)
        for (TreeNode left : allTrees(l))
            for (TreeNode right : allTrees(n - 1 - l)) {
                TreeNode root = new TreeNode(0);
                root.left = left;
                root.right = right;
                out.add(root);
            }
    return out;
}
</treenode></treenode>

🧠 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

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

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

  Single node? Congrats, it’s a tree.
• Memoization: If you already solved for n, return the answer.
  

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

  Save your sanity, and RAM.
• 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.
• 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.
• Store & return:

  memo[n] = result;
  return result;
  

  Memoized? Good. Ship it.

💻 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.

🧠 Interviewer Brain-Tattoo

“Look, if you’re generating the same subtree twice, you’re not optimizing — you’re just stubborn. Memoize or brace for a recursive apocalypse.”