All Possible Full Binary Trees

All Possible Full Binary Trees

What is this problem about?

The "All Possible Full Binary Trees interview question" is a recursive construction problem. A "Full Binary Tree" is a tree where every node has either 0 or 2 children. Given an integer n, you need to return a list of all possible full binary trees with exactly n nodes. If it's impossible to create a full binary tree with $n$ nodes (which happens when $n$ is even), you return an empty list.

Why is this asked in interviews?

Companies like Microsoft and Nvidia use the "All Possible Full Binary Trees coding problem" to test a candidate's ability to use recursion to solve combinatorial problems. It requires a deep understanding of how trees are structured and how to use "Divide and Conquer" to break a large problem (a tree with $n$ nodes) into smaller sub-problems (left and right subtrees).

Algorithmic pattern used

This problem uses Recursion with Memoization (Dynamic Programming on Trees).

1. Divide and Conquer: A tree with $n$ nodes has 1 root node and $n-1$ nodes distributed between the left and right subtrees.
2. Parity Check: Since every node adds 0 or 2 children, a full binary tree must always have an odd number of nodes. If $n$ is even, return [].
3. Recursive Step: For a given $n$, iterate through all possible odd values $i$ from 1 to $n-2$. Set $i$ nodes for the left subtree and $n-1-i$ nodes for the right subtree.
4. Combination: For every possible left subtree and every possible right subtree, create a new root node and attach them.
5. Memoization: Store the results for each $n$ in a hash map to avoid re-calculating the same tree structures multiple times.

Example explanation

For n = 3:

• Root uses 1 node. 2 nodes left.
• Only possible split: Left gets 1 node, Right gets 1 node.
• Left(1) returns a single leaf node. Right(1) returns a single leaf node.
• Combine: 1 possible tree (Root with two leaves). For n = 5:
• Split 1: Left(1), Right(3). (Combine 1 leaf with all trees of size 3).
• Split 2: Left(3), Right(1). (Combine all trees of size 3 with 1 leaf).

Common mistakes candidates make

• Not using Memoization: Without a cache, the number of recursive calls grows exponentially (following Catalan numbers), leading to a TLE.
• Incorrect node counting: Forgetting to subtract the root node when calculating the available nodes for children (using $n-i$ instead of $n-1-i$).
• Even $n$ case: Not recognizing that full binary trees cannot have an even number of nodes.

Interview preparation tip

When you see a problem asking for "all possible" configurations of a structure like a tree or expression, think about "Divide and Conquer." Practice problems like "Unique Binary Search Trees II" to get comfortable with the pattern of combining recursive results.