We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

All Possible Full Binary Trees

Number: 930

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Meta, Adobe, Apple, Google

Problem Description

Given an integer n, generate all possible full binary trees with n nodes. A full binary tree is defined as a binary tree where each node has either 0 or 2 children. Every node in the tree must have the value 0. Return the list of all possible full binary trees (each represented by its root), in any order.

Key Insights

  • A full binary tree can only be built with an odd number of nodes. Therefore, if n is even, no valid tree exists.
  • Use recursion to build trees: for n == 1, the only tree is a single node.
  • For n > 1, iterate over possible odd counts for the left subtree and let the right subtree use the remaining nodes.
  • Use memoization (caching) to avoid recomputing trees for the same number of nodes.
  • The number of full binary trees increases significantly with n, so careful recursion and caching are critical.

Space and Time Complexity

Time Complexity: O(2^(n/2)) in the worst-case scenario due to the combinatorial number of trees generated. Space Complexity: O(2^(n/2)) for storing generated trees in the memoization table and the recursive call stack.

Solution

We use a recursive approach combined with memoization. The base case is when n equals 1, where the only full binary tree is a single node. For n greater than 1, we iterate over odd counts of nodes for the left subtree (from 1 to n-2) and recursively generate all full binary trees for both left and right parts. Each combination of left and right subtree is then connected to a new root node to form a valid tree. The memoization table caches results for a given n to avoid redundant computations.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Recursive function to generate all full binary trees with n nodes.
def allPossibleFBT(n):
    # Dictionary for memoization.
    memo = {}

    def generate(num_nodes):
        # If result already computed for given num_nodes, return it.
        if num_nodes in memo:
            return memo[num_nodes]
        
        trees = []
        # Base case: only one tree possible with 1 node.
        if num_nodes == 1:
            trees.append(TreeNode(0))
        else:
            # Split nodes between left and right subtrees.
            for left_nodes in range(1, num_nodes, 2):
                right_nodes = num_nodes - 1 - left_nodes
                # Recursively generate left and right subtrees.
                left_subtrees = generate(left_nodes)
                right_subtrees = generate(right_nodes)
                # Combine each left and right subtree with a new root.
                for left in left_subtrees:
                    for right in right_subtrees:
                        root = TreeNode(0)
                        root.left = left
                        root.right = right
                        trees.append(root)
        # Save computed trees in memo.
        memo[num_nodes] = trees
        return trees

    return generate(n)

# Example usage:
# result = allPossibleFBT(7)
← Back to All Questions