algoadvance

Leetcode 894. All Possible Full Binary Trees

Problem Statement:

LeetCode 894 - All Possible Full Binary Trees

Given an integer n, return a list of all possible full binary trees with n nodes. Each node in a full binary tree has exactly 0 or 2 children.

Each element of the answer is the root node of one possible full binary 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:

Input: n = 7

Output: A list of all possible full binary trees with 7 nodes. The output format is a list of TreeNode objects, each representing the root of a full binary tree.

Clarifying Questions:

1. What are the constraints on n?

   • 1 <= n <= 20 (as per typical constraints seen in similar problems on LeetCode).
   • n is always odd (since only then a full binary tree is possible).

2. What should be the structure of the TreeNode class?

   • The TreeNode class usually has attributes like int val, TreeNode left, and TreeNode right.

3. Do nodes have any specific values?

   • No specific values are required, typically nodes value can just be 0 as we are interested in the structure.

Strategy:

• A full binary tree has an odd number of nodes.
• We can use a recursive approach to generate the trees.
• For each call, we will pick various numbers of nodes for the left subtree and the right subtree as candidates.
• Use dynamic programming (memoization) to store results of subproblems to avoid redundant calculations.

Code:

Here’s the Java solution with memoization to generate the list of all possible full binary trees:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    
    // Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() { this.val = 0; }
    }
    
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();
    
    public List<TreeNode> allPossibleFBT(int n) {
        // If n is even, it's impossible to form a full binary tree
        if (n % 2 == 0) {
            return new ArrayList<>();
        }
        
        // Memoization check
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Base case
        List<TreeNode> result = new ArrayList<>();
        if (n == 1) {
            result.add(new TreeNode());
        } else {
            for (int leftCount = 1; leftCount < n; leftCount += 2) {
                int rightCount = n - 1 - leftCount;
                for (TreeNode left : allPossibleFBT(leftCount)) {
                    for (TreeNode right : allPossibleFBT(rightCount)) {
                        TreeNode root = new TreeNode();
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
        }
        
        // Store result in memoization map
        memo.put(n, result);
        
        return result;
    }
    
    // Function to print the tree nodes for reference (optional)
    public void printTree(TreeNode root, String prefix) {
        if (root != null) {
            printTree(root.right, prefix + "    ");
            System.out.println(prefix + "+-- " + root.val);
            printTree(root.left, prefix + "    ");
        }
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<TreeNode> trees = solution.allPossibleFBT(7);
        System.out.println("Number of trees: " + trees.size());
        for (TreeNode tree : trees) {
            solution.printTree(tree, "");
            System.out.println();
        }
    }
}

Time Complexity:

The time complexity of this solution can be tricky to analyze exactly because it depends on the number of full binary trees that can be formed with n nodes. However, considering the recursive nature and memoization:

• Time Complexity: The solution is bounded by the Catalan number’s growth when considering unique BSTs which is approximately (O(2^n)) for a tree with n nodes.
• Space Complexity: (O(2^n)) to store the trees in the memo map.

This is an efficient approach given the constraints on n (1 to 20) due to the use of memoization.

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

• 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?