All Possible Full Binary Trees - Practice Coding Problems

All Possible Full Binary Trees - 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.

Input & Output

Example 1 — Small Tree

$ Input: n = 5

› Output: [[0,0,0,null,null,0,0],[0,0,0,0,0]]

💡 Note: With 5 nodes, we can create 2 different full binary trees: one with root having left subtree of 1 node and right subtree of 3 nodes, and another with left subtree of 3 nodes and right subtree of 1 node.

Example 2 — Single Node

$ Input: n = 1

› Output: [[0]]

💡 Note: Only one possible tree: a single root node with value 0.

Example 3 — Impossible Case

$ Input: n = 4

› Output: []

💡 Note: Cannot create a full binary tree with 4 nodes since full binary trees require an odd number of nodes (1 root + even number of children).

Constraints

1 ≤ n ≤ 20
n is guaranteed to be odd for non-empty results

Visualization

Tap to expand

Understanding the Visualization

Input Validation

Check if n is odd (full binary trees need odd nodes)

Split Strategy

Divide remaining n-1 nodes between left and right subtrees

Generate Trees

Create all combinations of valid left and right subtrees

Key Takeaway

🎯 Key Insight: Full binary trees require odd number of nodes and can be built by recursively combining all possible left-right subtree pairs

Asked in

f Facebook 15 a Amazon 12 G Google 8 M Microsoft 6

The key insight is that full binary trees need odd number of nodes and can be built by recursively generating left and right subtrees. The memoized approach caches results to avoid redundant calculations. Time: O(4ⁿ/n³/²), Space: O(4ⁿ/n³/²).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Generation	O(4ⁿ)	O(4ⁿ)	Generate all possible tree structures recursively without optimization
Memoized Recursion	O(4ⁿ/n³/²)	O(4ⁿ/n³/²)	Cache recursive results to avoid redundant computations

Recursive Generation — Algorithm Steps

Check if n is even (impossible for full binary tree)
Try all ways to split remaining n-1 nodes between left and right subtrees
Recursively generate all subtrees for each split
Combine every left subtree with every right subtree

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Validity

Verify n is odd (full binary trees need odd nodes)

Split Nodes

Divide remaining n-1 nodes between left and right subtrees

Generate Subtrees

Recursively create all possible left and right subtrees

Combine

Create root and attach every left-right combination

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode** solution(int n, int* returnSize) {
    *returnSize = 0;
    if (n % 2 == 0) {
        return NULL;
    }
    
    if (n == 1) {
        struct TreeNode** result = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
        result[0] = createNode(0);
        *returnSize = 1;
        return result;
    }
    
    struct TreeNode** result = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));
    int count = 0;
    
    for (int leftCount = 1; leftCount < n; leftCount += 2) {
        int rightCount = n - 1 - leftCount;
        
        int leftSize, rightSize;
        struct TreeNode** leftTrees = solution(leftCount, &leftSize);
        struct TreeNode** rightTrees = solution(rightCount, &rightSize);
        
        for (int i = 0; i < leftSize; i++) {
            for (int j = 0; j < rightSize; j++) {
                struct TreeNode* root = createNode(0);
                root->left = leftTrees[i];
                root->right = rightTrees[j];
                result[count++] = root;
            }
        }
    }
    
    *returnSize = count;
    return result;
}

void printTree(struct TreeNode* root) {
    if (!root) {
        printf("[]");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    printf("[");
    int first = 1;
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (!first) printf(",");
        first = 0;
        
        if (node) {
            printf("%d", node->val);
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            printf("null");
        }
    }
    printf("]");
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    struct TreeNode** trees = solution(n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printTree(trees[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4ⁿ)

Each recursive call branches into multiple subcalls, creating exponential growth

✓ Linear Growth

Space Complexity

O(4ⁿ)

Recursion stack depth and storage for all generated trees

✓ Linear Space

89.4K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler