Skip to main content
Talentd

All Possible Full Binary Trees - Solution & Explanation

MediumDynamic ProgrammingTreeRecursionMemoization15 min readAsked at: Amazon, Microsoft, NVIDIA +2
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaScript

Python

JavaScript

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.

The C++ solution utilizes a dynamic programming array dp where each entry dp[i] holds all the full binary trees possible with i nodes. Starting from the simplest case with one node, we iteratively combine smaller trees to build larger trees while ensuring balanced distribution between left and right subtrees, thereby leveraging previously computed solutions to optimize for new tree constructions.

Code

C++Java

C++

Java

Complexity

This method maintains a time complexity of O(2^N) and a space complexity of O(2^N) due to stored references of constructed trees. While iterative, it effectively mirrors the recursive/memoized strategies through explicit storage of previous calculations.

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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

This method maintains a time complexity of O(2^N) and a space complexity of O(2^N) due to stored references of constructed trees. While iterative, it effectively mirrors the recursive/memoized strategies through explicit storage of previous calculations.

Memoization Search—

Detailed Complexity Analysis

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

Video Solution

All Possible Full Binary Trees - Memoization - Leetcode 894 - Python • NeetCode • 41,351 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice All Possible Full Binary Trees with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching