894. All Possible Full Binary Trees


Problem Description

The problem asks to generate all possible "full binary trees" given an integer n, which represents the total number of nodes. Each node in these trees should have a value of 0. A "full binary tree" is defined as a binary tree where each node has either 0 or 2 children, meaning there are no nodes with only one child.

The goal is to produce a list of the root nodes of all distinct full binary trees that can be made with n nodes. It's important to note that the number of nodes n must be odd to form a full binary tree because each non-leaf node contributes exactly one additional node (the second child, since the first is balanced by the parent node being counted previously).

The results can be provided in any order, which indicates that the solution doesn't need to concern itself with sorting or maintaining a specific sequence for the trees.

Intuition

The solution uses recursion and memoization to efficiently generate all the combinations of full binary trees. Here's the thought process behind the approach:

  • Base Case: If n is 1, there is only one full binary tree possible, which is a single node with no children. This tree is added to the list of answers.

  • Recursion: If n is greater than 1, it must be an odd number for a full binary tree to be possible. Every full binary tree with n nodes has a root node, a left subtree, and a right subtree. Since the root consumes one node, the remaining n - 1 nodes must be divided between the left and right subtrees.

  • Generation of Subtrees: The algorithm iterates through all possible odd combinations of nodes that can form valid left and right subtrees. For example, if i nodes are used in the left subtree, then n - 1 - i nodes will be used in the right subtree. Recursion is used to generate all possible full binary trees for these two counts of nodes.

  • Combining Subtrees: For each combination of a left and a right subtree, a new tree is formed by creating a root node and attaching the left and right subtrees to it. All these new trees are added to the answer list for the current number of nodes n.

  • Memoization (@cache): To optimize the process, the algorithm uses memoization with the @cache decorator from Python's functools library. This prevents recalculation of the subtrees for the same n, as they are stored in the cache after the first computation. Therefore, any subsequent calls with the same number of nodes fetch the results directly from the cache.

By combining these steps, the algorithm efficiently constructs all possible full binary trees for any odd number n.

Solution Approach

The implementation of the solution for generating all possible full binary trees with n nodes employs recursion, memoization, and a straightforward iterative approach to build the trees. Let's dissect the code section by section:

  • Recursive Function (dfs): The dfs function is recursively called with the number of nodes n to compute all the possible subtrees with that node count. This function is where the trees are built from the bottom up.

    1@cache
    2def dfs(n: int) -> List[Optional[TreeNode]]:

    The @cache decorator is used here to memorize the results for each call with a specific n. This means that once we calculate all full binary trees with a certain number of nodes, we won't recalculate them again, significantly improving the efficiency of the algorithm.

  • Base Case: When n is 1, the function returns a list containing a single node with no children as the only possible full binary tree with one node.

    1if n == 1:
    2    return [TreeNode()]
  • Construction of Trees: If n is greater than 1, we initialize an empty list ans that will hold all full binary trees constructed for the current node count.

    1ans = []
  • Iterating Over Possible Left and Right Subtree Combinations: A for loop is used to iterate over all possible odd numbers of nodes that can be used for the left subtree (i), while ensuring the right subtree has the remainder (j = n - 1 - i).

    1for i in range(n - 1):
    2    j = n - 1 - i

    The range(n - 1) ensures we only consider an odd number of nodes for each subtree because n is odd, and if i is even, j will be odd, satisfying the requirement that both subtrees must also be full binary trees.

  • Combining Left and Right Subtrees: For each i, the recursive dfs call generates all possibilities for the left and right subtrees. We then loop through each possible pair of left and right subtrees and create a new tree with a root node that has these subtrees as children. This tree is appended to the ans list.

    1for left in dfs(i):
    2    for right in dfs(j):
    3        ans.append(TreeNode(0, left, right))
  • Returning All Possible Trees: Finally, the dfs function returns the ans list containing all the full binary trees for the given n.

    1return ans
  • Main Function: The main function allPossibleFBT calls the dfs recursive function and returns its result, which is the list of all possible full binary trees with n nodes.

    1def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
    2    return dfs(n)

By following this approach, the code generates all combinations in a way that is efficient both in terms of time, due to memoization, and in terms of understanding, as the code structure is intuitive and follows a simple pattern of combining smaller subtrees into larger trees.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using n = 3, which is the smallest number greater than 1 that can form a full binary tree.

  1. Recursive Function Call: The allPossibleFBT function is invoked with n = 3. Since n is greater than 1, we will be using the dfs function to find all possible full binary trees with 3 nodes.

  2. Check for Base Case: The dfs function is not immediately applicable to the base case, which is n = 1. Therefore, it does not return just a single node here and instead proceeds with constructing trees.

  3. Initialize Answer List: The function initializes an empty list ans to store all full binary trees for n = 3.

    1ans = []
  4. Iterate Over Possible Node Counts for Subtrees:

    1Since `n` is 3, we subtract 1 for the root node, leaving `n - 1` = 2 nodes to be distributed among the left and right subtrees. The loop will iterate through possible odd numbers for the left subtree:
    2
    3```python
    4for i in range(1, 2, 2):       # This loops only once since range(1, 2) yields just 1
    5    j = 3 - 1 - i              # j = 3 - 1 - 1 = 1

    This would yield i = 1 and j = 1.

  5. Generate Subtrees: The recursive function now generates all possible full binary trees (subtrees) with 1 node (base case). We know the answer is a single node since a single node without children is the only full binary tree possible with 1 node.

    1left_subtrees = dfs(1)    # Calls with i = 1, returns list of one node
    2right_subtrees = dfs(1)   # Calls with j = 1, returns list of one node
  6. Combine Subtrees: We loop through each left subtree paired with each right subtree, and for our case, it is just a single option. A new full binary tree is created for each pair with a new root node and the two subtrees as children.

    1for left in left_subtrees:
    2    for right in right_subtrees:
    3        ans.append(TreeNode(0, left, right))  # Appends a tree with root 0 and one child on each side
  7. Return Full Binary Trees: At the end of iteration, ans contains all full binary trees with n = 3, which in our case is just one tree:

    1Tree(0)
    2     / \
    3    0   0

    The dfs function thus returns this list (which contains a single tree structure) to the initial call of allPossibleFBT(3).

  8. Final Result: The allPossibleFBT function then returns this result, which is the list of all full binary trees with 3 nodes. In this case, there is only one such tree.

So the final output when calling allPossibleFBT(3) using the solution approach would be a list containing a single full binary tree with the root node and two children, as expected for n = 3 in a full binary tree.

Python Solution

1from functools import lru_cache
2from typing import List, Optional
3
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    # Generate all possible full binary trees with n nodes.
12    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
13        # Decorator for caching results of the function.
14        @lru_cache(None)
15        def buildFBT(total_nodes: int) -> List[Optional[TreeNode]]:
16            # If there is only one node, return list containing a single TreeNode.
17            if total_nodes == 1:
18                return [TreeNode()]
19          
20            # List to store all unique FBTs created from 'total_nodes' nodes.
21            full_binary_trees = []
22          
23            # Iterate over the number of nodes left after one is taken as the current root.
24            for nodes_in_left_subtree in range(total_nodes - 1):
25                nodes_in_right_subtree = total_nodes - 1 - nodes_in_left_subtree
26              
27                # Generate all full binary trees for the number of nodes in left subtree.
28                left_subtrees = buildFBT(nodes_in_left_subtree)
29                # Generate all full binary trees for the number of nodes in right subtree.
30                right_subtrees = buildFBT(nodes_in_right_subtree)
31              
32                # Combine each left subtree with each right subtree and add the current node as root.
33                for left in left_subtrees:
34                    for right in right_subtrees:
35                        full_binary_trees.append(TreeNode(0, left, right))
36          
37            # Return the list of all unique full binary trees.
38            return full_binary_trees
39
40        # Start generating FBTs starting with n nodes.
41        return buildFBT(n)
42

Java Solution

1import java.util.ArrayList;
2import java.util.List;
3
4/**
5 * Definition for a binary tree node.
6 */
7class TreeNode {
8    int val;
9    TreeNode left;
10    TreeNode right;
11
12    TreeNode() {}
13    TreeNode(int val) { this.val = val; }
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21class Solution {
22    // An array to store the results of subproblems.
23    private List<TreeNode>[] memo;
24
25    /**
26     * Generates all possible full binary trees with n nodes.
27     * 
28     * @param n The number of nodes in the full binary tree.
29     * @return A list of all possible full binary trees with n nodes.
30     */
31    public List<TreeNode> allPossibleFBT(int n) {
32        memo = new List[n + 1];
33        return buildTrees(n);
34    }
35
36    /**
37     * Helper method to recursively generate the full binary trees.
38     * 
39     * @param n The number of nodes to include in the tree.
40     * @return A list of all possible full binary trees with n nodes.
41     */
42    private List<TreeNode> buildTrees(int n) {
43        // The result is already computed; return the memoized result.
44        if (memo[n] != null) {
45            return memo[n];
46        }
47        // A tree with one node is a full binary tree by definition.
48        if (n == 1) {
49            return List.of(new TreeNode(0));
50        }
51
52        // Initialize a list to store all the generated trees.
53        List<TreeNode> result = new ArrayList<>();
54
55        // Split the remaining number of nodes between left and right subtrees.
56        // i represents the number of nodes in the left subtree.
57        for (int i = 0; i < n - 1; ++i) {
58            // j represents the number of nodes in the right subtree.
59            int j = n - 1 - i;
60          
61            // Recursively build left subtrees using i nodes.
62            for (TreeNode leftSubtree : buildTrees(i)) {
63                // Recursively build right subtrees using j nodes.
64                for (TreeNode rightSubtree : buildTrees(j)) {
65                    // Create a new tree with current node as the root.
66                    result.add(new TreeNode(0, leftSubtree, rightSubtree));
67                }
68            }
69        }
70
71        // Memoize and return the result.
72        return memo[n] = result;
73    }
74}
75

C++ Solution

1#include <vector>
2#include <functional>
3using namespace std;
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Main function that returns all possible full binary trees with 'n' nodes
17    vector<TreeNode*> allPossibleFBT(int n) {
18        // 'fullBinaryTrees' will store the full binary trees for each number of nodes from 1 to n
19        vector<vector<TreeNode*>> fullBinaryTrees(n + 1);
20
21        // Lambda function 'dfs' for depth-first search to build trees
22        function<vector<TreeNode*>(int)> dfs = [&](int totalNodes) -> vector<TreeNode*> {
23            // If we have calculated the full binary trees for 'totalNodes' then return them
24            if (!fullBinaryTrees[totalNodes].empty()) {
25                return fullBinaryTrees[totalNodes];
26            }
27
28            // A base case where there is only one node, return a single-node tree
29            if (totalNodes == 1) {
30                return vector<TreeNode*>{new TreeNode(0)};
31            }
32
33            // To store the answer for 'totalNodes' nodes
34            vector<TreeNode*> allTrees;
35
36            // Iterate through each combination of left/right subtree counts that sum to 'totalNodes - 1'
37            // Note that we exclude one node for the current tree's root
38            for (int leftTreeSize = 0; leftTreeSize < totalNodes - 1; ++leftTreeSize) {
39                int rightTreeSize = totalNodes - 1 - leftTreeSize;
40
41                // Get all full binary trees for left and right subtrees
42                for (auto leftSubtree : dfs(leftTreeSize)) {
43                    for (auto rightSubtree : dfs(rightTreeSize)) {
44                        // Make a new tree with '0' as root value and link the subtrees
45                        allTrees.push_back(new TreeNode(0, leftSubtree, rightSubtree));
46                    }
47                }
48            }
49
50            // Store the generated trees in 'fullBinaryTrees' for memoization and return them
51            return fullBinaryTrees[totalNodes] = allTrees;
52        };
53
54        // Start the depth-first search with 'n' nodes
55        return dfs(n);
56    }
57};
58

Typescript Solution

1// Definition for a binary tree node.
2class TreeNode {
3    val: number
4    left: TreeNode | null
5    right: TreeNode | null
6    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
7        this.val = (val === undefined ? 0 : val)
8        this.left = (left === undefined ? null : left)
9        this.right = (right === undefined ? null : right)
10    }
11}
12
13// Function to create all possible full binary trees with 'n' nodes.
14// Full binary trees are those where every node has either 0 or 2 children.
15function allPossibleFBT(n: number): Array<TreeNode | null> {
16    // Initialize an array to store all solutions for each n.
17    const solutionsCache: Array<Array<TreeNode | null>> = new Array(n + 1).fill(0).map(() => []);
18
19    // Helper function that uses Depth First Search to generate trees.
20    const generateFBT = (nodeCount: number): Array<TreeNode | null> => {
21        // If solutions for this node count are already computed, return them.
22        if (solutionsCache[nodeCount].length) {
23            return solutionsCache[nodeCount];
24        }
25        // Base case: If there is only one node, return a single TreeNode.
26        if (nodeCount === 1) {
27            solutionsCache[nodeCount].push(new TreeNode(0));
28            return solutionsCache[nodeCount];
29        }
30        // Initialize an array to hold the answer for the current node count.
31        const answers: Array<TreeNode | null> = [];
32
33        // Iterate over possible distributions of nodes between the left and right subtrees.
34        for (let i = 0; i < nodeCount - 1; ++i) {
35            const leftNodeCount = i;
36            const rightNodeCount = nodeCount - 1 - i;
37
38            // Perform DFS on left and right sides to build subtrees.
39            for (const leftSubtree of generateFBT(leftNodeCount)) {
40                for (const rightSubtree of generateFBT(rightNodeCount)) {
41                    // Assemble the subtrees with a new root node and add to answers.
42                    answers.push(new TreeNode(0, leftSubtree, rightSubtree));
43                }
44            }
45        }
46        // Memoize the answers for the current node count.
47        return (solutionsCache[nodeCount] = answers);
48    };
49
50    // Start generating all possible full binary trees with 'n' nodes.
51    return generateFBT(n);
52}
53

Time and Space Complexity

The given code defines a recursive function to generate all possible full binary trees with n nodes. A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Time Complexity:

The time complexity of this algorithm can be difficult to analyze due to the nature of the recursion that generates all possible combinations of left and right subtrees. However, it is possible to approximate it using Catalan numbers, which count the number of full binary trees with n nodes. If n is odd (since full binary trees can only have an odd number of nodes), then number of trees T(n) can be expressed using the nth Catalan number C((n-1)/2).

Given n nodes, we have T(n) = C((n-1)/2) as an approximation, since each node leads to a recursive call with fewer nodes, and the Catalan number gives a rough idea of the number of operations involved.

The time complexity to calculate the nth Catalan number can be roughly estimated to be O(n*2^(n)). Hence, the overall time complexity is O(n*2^(n)).

Space Complexity:

The space complexity includes the memory used by the recursion stack, as well as the space used to store all possible subtrees.

  1. Recursion Stack: Each call to dfs will use a certain amount of stack space. Since the function is called recursively, the maximum depth of the recursion stack would be proportional to n.

  2. All Possible Trees: Additionally, since we save all possible full binary trees, the space taken by these trees is also significant. The number of trees is given by the nth Catalan number, and since we store each tree, we need to have space for all of them.

Thus, the space complexity can be approximated as O(n*2^(n)) as well, since for larger n, the dominant factor will be the storage of the trees (which is essentially the same as the time complexity because of the way we are generating the trees).

Note: The @cache decorator is used to cache results of subproblems, which optimizes both time and space by avoiding recomputation. The caching could improve time complexity in practice but doesn't change the overall worst-case time complexity.

Overall, the complexities are roughly estimated due to the involvement of Catalan numbers, but they give an idea about how the algorithm scales with respect to n.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫