algoadvance

You are given an integer n. A full binary tree is a binary tree where every node has either 0 or 2 children.

Return a list of all possible full binary trees with n nodes. Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

Each node of each tree in the answer must have Node.val == 0.

Example:

Input: n = 7 Output: A list of all possible full binary trees with 7 nodes.

Constraints:

• 1 <= n <= 20

Clarifying Questions

1. What is a full binary tree? A full binary tree is a binary tree where each node has exactly 0 or 2 children.

2. Is the value of each node significant? For the purpose of returning possible trees, each node’s value must be 0.

3. Are we allowed to return the trees in any order? Yes, the trees can be returned in any order.

4. What should be the structure of the returned list? Each element in the list should be the root node of one possible tree.

Strategy

1. Recursive Approach:
   • Use recursion to generate all possible full binary trees.
   • Base case: If n is 1, return a tree with a single node.
   • Recursive case: For each possible split of n-1 nodes between the left and right subtrees, recursively generate all combinations of full binary trees for those splits.
   • Combine the left and right subtrees by attaching them to a new root node.
2. Memoization:
   • Use a memoization dictionary to avoid redundant computations.

Let’s implement this solution in Python.

Code

from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def allPossibleFBT(n: int) -> List[TreeNode]:
    if n % 2 == 0:
        return []
    
    memo = {}

    def build_FBT(n):
        if n == 1:
            return [TreeNode(0)]
        if n in memo:
            return memo[n]
        
        result = []
        for left_tree_size in range(1, n, 2):
            right_tree_size = n - 1 - left_tree_size
            for left in build_FBT(left_tree_size):
                for right in build_FBT(right_tree_size):
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    result.append(root)
        memo[n] = result
        return result

    return build_FBT(n)

Time Complexity

The time complexity of this solution is difficult to analyze exactly due to the nature of the recursion and memoization, but generally:

• Upper Bound: The worst-case scenario is generally exponential, approximately O(2^(n/2)), because each node in the tree can have multiple combinations of left and right subtrees.
• Memoization Impact: Memoization significantly reduces the number of recursive calls by storing previously computed results, making the effective time complexity much better than the theoretical exponential bound.

The space complexity is primarily driven by recursive stack depth and memoization storage, making it roughly O(n * 2^(n/2)) in the worst case.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?