algoadvance

Leetcode 894. All Possible Full Binary Trees

Problem Statement

LeetCode 894: All Possible Full Binary Trees

A full binary tree is a binary tree where each node has exactly 0 or 2 children. 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 with n nodes must have exactly n nodes with n being an odd integer, otherwise return an empty list.

Clarifying Questions

  1. Do we need to implement the tree node structure, or is it provided?
    • TreeNode structure is standard and typically provided in such problems.
  2. How do we need to represent the output? As trees or some serialized format?
    • The output should be a list of root nodes of the full binary trees.

Strategy

To solve this problem, we can use a recursive approach:

  1. Base Case:
    • If n == 1, return a list with a single node tree because a single node without children is a valid full binary tree.
  2. Recursive Case:
    • For each tree structure, the root node will have two subtrees. We will recursively generate all combinations of left and right subtrees. For a tree with n nodes:
      • We can have the left subtree with i nodes and the right subtree with n-1-i nodes (since including the root, total nodes are n).
  3. Memoization:
    • Use a memoization technique to store results for each n to avoid recomputation and thus optimizing the solution.

Code

#include <vector>
using namespace std;

// 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*> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return {}; // No full binary trees possible with even number of nodes
        }
        
        // Memoization to store already computed results
        static unordered_map<int, vector<TreeNode*>> memo;
        
        // If already computed, return the result from the map
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        
        vector<TreeNode*> result;
        
        // Base case: Only one full binary tree possible with 1 node
        if (n == 1) {
            result.push_back(new TreeNode(0));
            memo[n] = result;
            return result;
        }
        
        // Recursively construct all full binary trees
        for (int leftNodes = 1; leftNodes < n; leftNodes += 2) {
            int rightNodes = n - 1 - leftNodes;
            // Generate left and right subtrees for each valid combination
            vector<TreeNode*> leftTrees = allPossibleFBT(leftNodes);
            vector<TreeNode*> rightTrees = allPossibleFBT(rightNodes);
            // Combine left and right subtrees with the current root
            for (auto leftTree : leftTrees) {
                for (auto rightTree : rightTrees) {
                    TreeNode* root = new TreeNode(0);
                    root.left = leftTree;
                    root.right = rightTree;
                    result.push_back(root);
                }
            }
        }
        
        // Store the computed result before returning
        memo[n] = result;
        return result;
    }
};

Time Complexity

This solution ensures that all possible full binary trees with n nodes are generated efficiently using recursive construction and memoization techniques.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI