All Possible Full Binary Trees LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Google NvidiaViews 3021

Problem Statement:

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

Examples:

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

All Possible Full Binary Trees LeetCode Solution

Approach:

Idea:

The problem can be solved with the help of recursion. The point to remember is that an FBT (Full binary tree) can only be built if the numbers of nodes are odd. The idea is to consider position i, such that we can distribute an odd number of nodes on either side of the ith node and then can calculate the same recursively for the children. In the end, we can simply combine all the results.

Say we need to find out all possible FBTs for 7 nodes [1,2,3,4,5,6,7].
It is a combination of all FBTs rooted at 1 and rooted at 2 …at 7. For example, to get all FBTs rooted at 4, we can iterate through all FBTs of size 3 (node1, node2, node3) as our left child and for each of such tree, we can iterate through all FBTs of size 3 (node5, node6, node7) as our right child.

Since it is a full binary tree, in our case below, we need to add the tree at the current node only when left and right are both null or non-null.

Code:

All Possible Full Binary Trees C++ Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> helper(int n){
        if(n==1)
            return {new TreeNode(0)};
        vector<TreeNode*> ans;
        for(int i=1;i<n;i+=2){
            vector<TreeNode*> left = helper(i);
            vector<TreeNode*> right = helper(n-i-1);
            for(auto l:left){
                for(auto r:right){
                    TreeNode* root = new TreeNode();
                    root->left = l;
                    root->right = r;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
    vector<TreeNode*> allPossibleFBT(int n) {
        return helper(n);
    }
};

 

Complexity Analysis of All Possible Full Binary Trees LeetCode Solution:

Translate »