894. All Possible Full Binary Trees LeetCode Solution

In this guide, you will get 894. All Possible Full Binary Trees LeetCode Solution with the best time and space complexity. The solution to All Possible Full Binary Trees problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
All Possible Full Binary Trees solution in C++
All Possible Full Binary Trees solution in Java
All Possible Full Binary Trees solution in Python
Additional Resources

894. All Possible Full Binary Trees LeetCode Solution image

Problem Statement of All Possible Full Binary Trees

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

Constraints:

1 <= n <= 20

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

894. All Possible Full Binary Trees LeetCode Solution in C++

class Solution {
 public:
  vector<TreeNode*> allPossibleFBT(int n) {
    if (n % 2 == 0)
      return {};
    if (n == 1)
      return {new TreeNode(0)};
    if (const auto it = mem.find(n); it != mem.cend())
      return it->second;

    vector<TreeNode*> ans;

    for (int leftCount = 0; leftCount < n; ++leftCount) {
      const int rightCount = n - 1 - leftCount;
      for (TreeNode* left : allPossibleFBT(leftCount))
        for (TreeNode* right : allPossibleFBT(rightCount)) {
          ans.push_back(new TreeNode(0));
          ans.back()->left = left;
          ans.back()->right = right;
        }
    }

    return mem[n] = ans;
  }

 private:
  unordered_map<int, vector<TreeNode*>> mem;
};
/* code provided by PROGIEZ */

894. All Possible Full Binary Trees LeetCode Solution in Java

class Solution {
  public List<TreeNode> allPossibleFBT(int n) {
    if (n % 2 == 0)
      return new ArrayList<>();
    if (n == 1)
      return Arrays.asList(new TreeNode(0));
    if (mem.containsKey(n))
      return mem.get(n);

    List<TreeNode> ans = new ArrayList<>();

    for (int leftCount = 0; leftCount < n; ++leftCount) {
      final int rightCount = n - 1 - leftCount;
      for (TreeNode left : allPossibleFBT(leftCount))
        for (TreeNode right : allPossibleFBT(rightCount)) {
          ans.add(new TreeNode(0));
          ans.get(ans.size() - 1).left = left;
          ans.get(ans.size() - 1).right = right;
        }
    }

    mem.put(n, ans);
    return ans;
  }

  private Map<Integer, List<TreeNode>> mem = new HashMap<>();
}
// code provided by PROGIEZ

894. All Possible Full Binary Trees LeetCode Solution in Python

class Solution:
  @functools.lru_cache(None)
  def allPossibleFBT(self, n: int) -> list[TreeNode | None]:
    if n % 2 == 0:
      return []
    if n == 1:
      return [TreeNode(0)]

    ans = []

    for leftCount in range(n):
      rightCount = n - 1 - leftCount
      for left in self.allPossibleFBT(leftCount):
        for right in self.allPossibleFBT(rightCount):
          ans.append(TreeNode(0))
          ans[-1].left = left
          ans[-1].right = right

    return ans
 # code by PROGIEZ