All Possible Full Binary Trees

Medium · 1-D Dynamic Programming · Explanation and code example

Dynamic Programming (Bottom-Up)

How it works

Instead of recursing from n down and caching, we can build solutions bottom-up. We start with the base case (n=1), then iteratively compute solutions for n=3, 5, 7, ... up to the target.

For each odd value, we combine previously computed smaller trees to form larger ones. Since we only ever need results for smaller odd numbers, and we compute them in order, all dependencies are satisfied when we need them.

Steps

  1. If n is even, return an empty list.
  2. Create an array dp where dp[i] will store all full binary trees with i nodes.
  3. Initialize dp[1] with a single node.
  4. For nodes from 3 to n, stepping by 2:
    • For left from 1 to nodes-1, stepping by 2:
      • Set right = nodes - 1 - left.
      • For each tree in dp[left] and each tree in dp[right]:
        • Create a new root combining them and add to dp[nodes].
  5. Return dp[n].

Complexity

  • Time complexity: O(2 ^ n)
  • Space complexity: O(n * 2 ^ n)

Things to watch for

Forgetting That Full Binary Trees Require Odd Node Counts

A full binary tree can only exist when n is odd. Each node either has 0 or 2 children, so starting with 1 root and adding pairs means the total is always odd. Failing to check this leads to wasted computation or incorrect results.

Reusing Tree Nodes Across Different Results

When combining left and right subtrees, you must create a new root node for each combination. Reusing the same node object causes all trees to share structure, corrupting the results.

Iterating Over Even Values for Subtree Sizes

In a full binary tree, both left and right subtrees must also be full binary trees, meaning they need odd node counts. Iterating over all values instead of only odd values wastes time and produces empty results for even sizes.

Python code example

from typing import List, 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]]:
        if n % 2 == 0:
            return []

        dp = [[] for _ in range(n + 1)]
        dp[1] = [TreeNode(0)]

        for nodes in range(3, n + 1, 2):
            res = []
            for left in range(1, nodes, 2):
                right = nodes - 1 - left
                for t1 in dp[left]:
                    for t2 in dp[right]:
                        res.append(TreeNode(0, t1, t2))
            dp[nodes] = res

        return dp[n]

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return {};
        }

        vector<vector<TreeNode*>> dp(n + 1);
        dp[1].push_back(new TreeNode(0));

        for (int nodes = 3; nodes <= n; nodes += 2) {
            vector<TreeNode*> res;
            for (int left = 1; left < nodes; left += 2) {
                int right = nodes - 1 - left;
                for (auto& t1 : dp[left]) {
                    for (auto& t2 : dp[right]) {
                        res.push_back(new TreeNode(0, t1, t2));
                    }
                }
            }
            dp[nodes] = res;
        }

        return dp[n];
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations