All Possible Full Binary Trees Solution | LeetCode-894: Medium | JavaScript Implementation

We will be seeing the solution to the LeetCode problem 894 in JavaScript. I hope you will find it useful.

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.

Link to Problem: https://leetcode.com/problems/course-schedule-ii/

Implementation:

var allPossibleFBT = function(n) {
    const util = (n)=>{
        if(n==1){
            return ([new TreeNode(0)])
        }
        let ans = [];
        for(let i = 1;i<n;i=i+2){
            let leftNodes = util(i)
            let rightNodes = util(n-i-1)
            for(let leftNode of leftNodes){
                for(let rightNode of rightNodes){
                    let root = new TreeNode(0);
                    root.left = leftNode;
                    root.right = rightNode;
                    ans.push(root)
                }
            }
        }
        return ans
    }
    return util(n)
    
};

Implementation with Memorisation:

var allPossibleFBT = function(n) {
    let memo = [];
    const util = (n)=>{
        if(n==1){
            return ([new TreeNode(0)])
        }
        if(memo[n]){
            return memo[n]
        }
        let ans = [];
        for(let i = 1;i<n;i=i+2){
            let leftNodes = util(i)
            let rightNodes = util(n-i-1)
            for(let leftNode of leftNodes){
                for(let rightNode of rightNodes){
                    let root = new TreeNode(0);
                    root.left = leftNode;
                    root.right = rightNode;
                    ans.push(root)
                }
            }
        }
        memo[n] = ans
        return memo[n]
    }
    return util(n)
    
};

Thank you for reading hope this code is helpful to you.