894. All Possible Full Binary Trees Solution

The problem

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

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]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

Constraints:

1 <= n <= 20

Approach overview

Problem Overview: You are given an odd integer n. Build and return every possible full binary tree with exactly n nodes. A full binary tree means every node has either 0 or 2 children. The result is a list of root nodes representing all valid structures.

Approach 1: Recursive Construction with Memoization (Time: ~O(n * F(n)), Space: ~O(n * F(n)))

The key observation: a full binary tree always contains an odd number of nodes. If the root uses one node, the remaining n-1 nodes must be split between the left and right subtrees, and both subtree sizes must also be odd. Recursively generate all left subtrees of size i and all right subtrees of size n-1-i, then attach each combination to a new root. This naturally forms a Cartesian product of left and right subtree possibilities.

Naive recursion recomputes the same subtree sizes many times. Add caching (memoization) keyed by n. When the function needs trees with k nodes, it first checks the cache and reuses previously generated lists. This drastically reduces recomputation and is the most common interview solution using recursion with memoization.

Approach 2: Dynamic Programming (Iterative Build) (Time: ~O(n * F(n)), Space: ~O(n * F(n)))

The recursive idea can be converted into bottom‑up dynamic programming. Maintain a DP array where dp[i] stores all full binary trees with i nodes. Start with the base case dp[1] containing a single node tree. Then iterate through odd sizes from 3 to n.

For each size i, try every odd split left and right = i - 1 - left. Combine each tree from dp[left] with each tree from dp[right] under a new root node. Append the constructed trees into dp[i]. This approach avoids recursion and makes the dependency structure explicit while still generating every valid binary tree configuration.

Recommended for interviews: Recursive generation with memoization is the expected approach. It directly models the recursive structure of full binary trees and demonstrates understanding of subtree decomposition and caching. Mention the odd-node constraint first, then describe splitting n-1 nodes across left and right subtrees. The iterative DP version shows deeper understanding but usually comes after explaining the recursive insight.

Approach 1: Recursive Approach with Caching

This approach uses recursion to build all possible full binary trees for a given number of nodes. Since the problem exhibits overlapping subproblems, we can optimize the solution using memoization to store the results of previously solved subproblems. This significantly reduces the number of calculations needed.

Python

from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

memo = {}

def allPossibleFBT(N: int) -> List[TreeNode]:
    if N % 2 == 0:
        return []
    if N == 1:
        return [TreeNode(0)]
    if N in memo:
        return memo[N]

    result = []
    for left in range(1, N, 2):
        for left_subtree in allPossibleFBT(left):
            for right_subtree in allPossibleFBT(N - 1 - left):
                root = TreeNode(0)
                root.left = left_subtree
                root.right = right_subtree
                result.append(root)

    memo[N] = result
    return result

JavaScript

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const memo = {};

function allPossibleFBT(N) {
  if (N % 2 === 0) return [];
  if (N === 1) return [new TreeNode(0)];
  if (memo[N]) return memo[N];

  const result = [];
  for (let left = 1; left < N; left += 2) {
    for (let leftNode of allPossibleFBT(left)) {
      for (let rightNode of allPossibleFBT(N - 1 - left)) {
        const root = new TreeNode(0);
        root.left = leftNode;
        root.right = rightNode;
        result.push(root);
      }
    }
  }
  memo[N] = result;
  return result;
}

The Python function allPossibleFBT uses recursion and memoization to find all full binary trees of size N. The base case is when N is 1, where there's only one full binary tree possible, which consists of a single node. We recursively solve for every odd N, considering each odd number left as a candidate for the number of nodes in the left subtree and recursively constructing left and right subtrees. Every tree is combined with a new root node, creating a list of solutions that is cached in memo for future reference.

Complexity

The time complexity is O(2^N) due to the recursive generation of all possible subtrees. However, memoization helps to reduce the number of redundant calculations. The space complexity is also O(2^N) due to the storage of previously computed subtrees in the memo dictionary.

Try this approach in the editor

Approach 2: Dynamic Iterative Approach

This approach uses dynamic programming through an iterative method to build trees from the bottom up. We generate trees with increasingly larger numbers of nodes by combining smaller full binary trees, ensuring that each construction step builds on the last.

Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public List<TreeNode> allPossibleFBT(int N) {
    List<TreeNode>[] dp = new ArrayList[N + 1];
    for (int i = 0; i <= N; i++) dp[i] = new ArrayList<>();
    if (N % 2 == 0) return dp[N];
    dp[1].add(new TreeNode(0));
    for (int n = 3; n <= N; n += 2) {
        for (int left = 1; left < n; left += 2) {
            for (TreeNode leftNode : dp[left]) {
                for (TreeNode rightNode : dp[n - left - 1]) {
                    TreeNode root = new TreeNode(0);
                    root.left = leftNode;
                    root.right = rightNode;
                    dp[n].add(root);
                }
            }
        }
    }
    return dp[N];
}

C++

#include <vector>
using namespace std;

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) {}
};

vector<TreeNode*> allPossibleFBT(int N) {
    vector<vector<TreeNode*>> dp(N + 1);
    if (N % 2 == 0) return {};
    dp[1] = {new TreeNode(0)};
    for (int n = 3; n <= N; n += 2) {
        vector<TreeNode*> result;
        for (int left = 1; left < n; left += 2) {
            for (auto* leftTree : dp[left]) {
                for (auto* rightTree : dp[n - left - 1]) {
                    TreeNode* root = new TreeNode(0);
                    root->left = leftTree;
                    root->right = rightTree;
                    result.push_back(root);
                }
            }
        }
        dp[n] = result;
    }
    return dp[N];
}

In this Java solution, an array of lists dp is used to store trees. Each tree is represented by a TreeNode with zero value. This iterative process combines smaller trees at each step to build bigger trees, ensuring that all trees have the characteristic of full binary trees, which inherently coordinates the nodes' distribution between left and right subtrees.

Complexity

The iterative dynamic programming approach figures time complexity as O(2^N) in generating possible trees and maintains space complexity O(2^N) for saving the results of these trees in dp.

Try this approach in the editor

Approach 3: Memoization Search

If n=1, return a list with a single node directly.

If n > 1, we can enumerate the number of nodes i in the left subtree, then the number of nodes in the right subtree is n-1-i. For each case, we recursively construct all possible genuine binary trees for the left and right subtrees. Then we combine the left and right subtrees in pairs to get all possible genuine binary trees.

This process can be optimized with memoization search to avoid repeated calculations.

The time complexity is O(\frac{2^n}{\sqrt{n}}), and the space complexity is O(\frac{2^n}{\sqrt{n}}). Where n is the number of nodes.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function allPossibleFBT(n: number): Array<TreeNode | null> {
    const f: Array<Array<TreeNode | null>> = new Array(n + 1).fill(0).map(() => []);
    const dfs = (n: number): Array<TreeNode | null> => {
        if (f[n].length) {
            return f[n];
        }
        if (n === 1) {
            f[n].push(new TreeNode(0));
            return f[n];
        }
        const ans: Array<TreeNode | null> = [];
        for (let i = 0; i < n - 1; ++i) {
            const j = n - 1 - i;
            for (const left of dfs(i)) {
                for (const right of dfs(j)) {
                    ans.push(new TreeNode(0, left, right));
                }
            }
        }
        return (f[n] = ans);
    };
    return dfs(n);
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private List<TreeNode>[] f;

    public IList<TreeNode> AllPossibleFBT(int n) {
        f = new List<TreeNode>[n + 1];
        return Dfs(n);
    }

    private IList<TreeNode> Dfs(int n) {
        if (f[n] != null) {
            return f[n];
        }

        if (n == 1) {
            return new List<TreeNode> { new TreeNode() };
        }

        List<TreeNode> ans = new List<TreeNode>();
        for (int i = 0; i < n - 1; ++i) {
            int j = n - 1 - i;
            foreach (var left in Dfs(i)) {
                foreach (var right in Dfs(j)) {
                    ans.Add(new TreeNode(0, left, right));
                }
            }
        }
        f[n] = ans;
        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func allPossibleFBT(n int) []*TreeNode {
	f := make([][]*TreeNode, n+1)
	var dfs func(int) []*TreeNode
	dfs = func(n int) []*TreeNode {
		if len(f[n]) > 0 {
			return f[n]
		}
		if n == 1 {
			return []*TreeNode{&TreeNode{Val: 0}}
		}
		ans := []*TreeNode{}
		for i := 0; i < n-1; i++ {
			j := n - 1 - i
			for _, left := range dfs(i) {
				for _, right := range dfs(j) {
					ans = append(ans, &TreeNode{0, left, right})
				}
			}
		}
		f[n] = ans
		return ans
	}
	return dfs(n)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut f: Vec<Option<Vec<Option<Rc<RefCell<TreeNode>>>>>> = vec![None; (n + 1) as usize];
        Self::dfs(n, &mut f)
    }

    fn dfs(
        n: i32,
        f: &mut Vec<Option<Vec<Option<Rc<RefCell<TreeNode>>>>>>,
    ) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        if let Some(ref result) = f[n as usize] {
            return result.clone();
        }

        let mut ans = Vec::new();
        if n == 1 {
            ans.push(Some(Rc::new(RefCell::new(TreeNode::new(0)))));
            return ans;
        }

        for i in 0..n - 1 {
            let j = n - 1 - i;
            for left in Self::dfs(i, f).iter() {
                for right in Self::dfs(j, f).iter() {
                    let new_node = Some(Rc::new(RefCell::new(TreeNode {
                        val: 0,
                        left: left.clone(),
                        right: right.clone(),
                    })));
                    ans.push(new_node);
                }
            }
        }
        f[n as usize] = Some(ans.clone());
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Approach with Caching	The time complexity is `O(2^N)` due to the recursive generation of all possible subtrees. However, memoization helps to reduce the number of redundant calculations. The space complexity is also `O(2^N)` due to the storage of previously computed subtrees in the `memo` dictionary.
Dynamic Iterative Approach	The iterative dynamic programming approach figures time complexity as `O(2^N)` in generating possible trees and maintains space complexity `O(2^N)` for saving the results of these trees in `dp`.
Memoization Search	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive with Memoization	~O(n * F(n))	~O(n * F(n))	Most intuitive solution. Preferred in interviews when explaining recursive tree construction.
Dynamic Programming (Iterative)	~O(n * F(n))	~O(n * F(n))	When avoiding recursion or demonstrating bottom-up DP construction of tree structures.

Frequently asked questions

Is All Possible Full Binary Trees easy or hard?

All Possible Full Binary Trees is rated Medium on LeetCode but conceptually challenging if you are new to recursive tree generation. Understanding the odd-node constraint and applying memoization makes the solution manageable.

All Possible Full Binary Trees Python/Java solution

In Python or Java, implement a recursive function that returns all trees with n nodes and store results in a memoization map. For each odd split of nodes between left and right, combine every left subtree with every right subtree under a new root node.

How to solve All Possible Full Binary Trees in O(n)?

Generating all full binary trees cannot be done in strict O(n) time because the output size itself grows exponentially. Any correct solution must build every valid tree structure. The best practical approach uses memoized recursion or dynamic programming with complexity proportional to the number of generated trees.

What is the best approach for All Possible Full Binary Trees?

Recursive generation with memoization is the most common and interview-friendly approach. For each odd split of nodes between left and right subtrees, recursively build all combinations and cache results by node count. This avoids recomputation and efficiently constructs every valid tree.

Is All Possible Full Binary Trees asked at Google/Amazon/Meta?

Tree construction and recursion problems similar to this appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of generating tree structures using recursion and memoization is a common interview topic.

What data structure is used in All Possible Full Binary Trees?

The problem uses the binary tree data structure combined with recursion and memoization or dynamic programming. A hash map or dictionary typically stores previously computed lists of trees keyed by the number of nodes.

What is the time complexity of All Possible Full Binary Trees?

The complexity depends on the number of full binary trees that can be formed. The algorithm generates every valid tree, which follows a Catalan-like growth pattern. The practical complexity is roughly O(n * F(n)), where F(n) is the number of full binary trees for n nodes.

All Possible Full Binary Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach with Caching

Approach 2: Dynamic Iterative Approach

Approach 3: Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

All Possible Full Binary Trees solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach with Caching

Approach 2: Dynamic Iterative Approach

Approach 3: Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems