Leetcode•Jul 04, 2026

All Possible Full Binary Trees

Hazrat Ali

Leetcode

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

Solution
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var allPossibleFBT = function(n) {
    const memo = new Map();

    function build(nodes) {
        if (memo.has(nodes)) return memo.get(nodes);

        const res = [];

        if (nodes === 1) {
            res.push(new TreeNode(0));
        } else if (nodes % 2 === 1) {
            for (let leftNodes = 1; leftNodes < nodes; leftNodes += 2) {
                const rightNodes = nodes - 1 - leftNodes;

                const leftTrees = build(leftNodes);
                const rightTrees = build(rightNodes);

                for (const left of leftTrees) {
                    for (const right of rightTrees) {
                        res.push(new TreeNode(0, left, right));
                    }
                }
            }
        }

        memo.set(nodes, res);
        return res;
    }

    return build(n);
};



Comments