All Possible Full Binary Trees - Video Solutions

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.