All Possible Full Binary Trees

medium dynamic programming recursion trees memoization

Problem

Given an integer n, return a list of all structurally unique full binary trees with exactly n nodes. A full binary tree is one in which every node has either 0 or 2 children. Each node's value can be 0. You may return the trees in any order.

Inputn = 7

Output5 distinct full binary trees

A full binary tree exists only for odd n. The count of shapes follows the Catalan-like sequence 1, 1, 2, 5, 14, … for n = 1, 3, 5, 7, 9.

n (odd, 1–13)

from functools import cache

class Solution:
    def allPossibleFBT(self, n):
        if n % 2 == 0:
            return []

        @cache
        def build(k):
            if k == 1:
                return (TreeNode(0),)
            trees = []
            for left in range(1, k - 1, 2):
                right = k - 1 - left
                for l in build(left):
                    for r in build(right):
                        node = TreeNode(0)
                        node.left, node.right = l, r
                        trees.append(node)
            return tuple(trees)

        return list(build(n))

function allPossibleFBT(n) {
  if (n % 2 === 0) return [];
  const memo = new Map();

  function build(k) {
    if (memo.has(k)) return memo.get(k);
    if (k === 1) return [new TreeNode(0)];
    const trees = [];
    for (let left = 1; left < k - 1; left += 2) {
      const right = k - 1 - left;
      for (const l of build(left)) {
        for (const r of build(right)) {
          const node = new TreeNode(0);
          node.left = l; node.right = r;
          trees.push(node);
        }
      }
    }
    memo.set(k, trees);
    return trees;
  }

  return build(n);
}

class Solution {
    Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) return new ArrayList<>();
        if (memo.containsKey(n)) return memo.get(n);
        List<TreeNode> trees = new ArrayList<>();
        if (n == 1) {
            trees.add(new TreeNode(0));
        } else {
            for (int left = 1; left < n - 1; left += 2) {
                int right = n - 1 - left;
                for (TreeNode l : allPossibleFBT(left)) {
                    for (TreeNode r : allPossibleFBT(right)) {
                        TreeNode node = new TreeNode(0);
                        node.left = l; node.right = r;
                        trees.add(node);
                    }
                }
            }
        }
        memo.put(n, trees);
        return trees;
    }
}

class Solution {
    unordered_map<int, vector<TreeNode*>> memo;
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (n % 2 == 0) return {};
        if (memo.count(n)) return memo[n];
        vector<TreeNode*> trees;
        if (n == 1) {
            trees.push_back(new TreeNode(0));
        } else {
            for (int left = 1; left < n - 1; left += 2) {
                int right = n - 1 - left;
                for (TreeNode* l : allPossibleFBT(left))
                    for (TreeNode* r : allPossibleFBT(right)) {
                        TreeNode* node = new TreeNode(0);
                        node->left = l; node->right = r;
                        trees.push_back(node);
                    }
            }
        }
        return memo[n] = trees;
    }
};

Explanation

A full binary tree has every node owning either 0 or 2 children. To build all such trees with n nodes, we think recursively: one node is the root, and the remaining n - 1 nodes get divided between a left subtree and a right subtree.

Both subtrees must themselves be full binary trees, so both need an odd number of nodes. That is why the loop runs left over 1, 3, 5, ... with range(1, k - 1, 2), and sets right = k - 1 - left.

For each split we take every possible left-shape l and pair it with every possible right-shape r, attach them to a fresh root, and collect that tree. This "all lefts × all rights" combining is what generates every distinct shape.

The base case build(1) is a single leaf. Also, if n is even no full binary tree exists, so we return an empty list right away. The @cache decorator memoizes build(k) so each size is only constructed once.

Example: n = 7. The splits of the other 6 nodes are (1,5), (3,3), (5,1), and combining the sub-shapes yields 5 distinct full binary trees.

Time: O(2ⁿ) Space: O(2ⁿ)