Jobs

Interviews

Discussions

Unique Binary Search Trees II

Medium

Unique Binary Search Trees II

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'n'? Could 'n' be zero or negative?
If 'n' is zero, should I return an empty list, or a list containing a single null node?
Are the BSTs returned expected to be unique in terms of their structure, or just their node values?
Is there a specific order required for the list of BSTs returned?
Will the input 'n' ever be so large that the number of possible trees would cause a memory overflow?

Brute Force Solution

Approach

The brute force approach to generating unique binary search trees involves creating every single possible tree shape with the given numbers. We explore every combination of numbers as the root and then recursively do the same for the left and right subtrees. We keep all the unique tree structures we create.

Here's how the algorithm would work step-by-step:

Consider each number as a possible root of the binary search tree.
For each number we pick as the root, separate the remaining numbers into two groups: those smaller (for the left subtree) and those larger (for the right subtree).
Now, for each group of numbers (the smaller ones and the larger ones), repeat the same process: try each number in the group as a root for a subtree, and split the remaining numbers into even smaller left and right groups.
Keep doing this until you have no numbers left. This represents the base case for an empty subtree.
Each time you pick a root and build left and right subtrees, combine them to form a complete binary search tree. Remember that you need to explore all possible combinations of left and right subtrees for a given root.
Store each unique tree you create. Since we are exploring all possibilities, we will generate all valid binary search trees.
Finally, return the collection of all the unique binary search trees you've stored.

Code Implementation

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

def generate_unique_bsts(number):
    if number == 0:
        return []
    
    def generate_trees(start, end):
        if start > end:
            return [None]
        
        all_trees = []
        
        # Iterate through all possible root nodes
        for root_value in range(start, end + 1):
            # Generate all possible left subtrees
            left_subtrees = generate_trees(start, root_value - 1)

            # Generate all possible right subtrees
            right_subtrees = generate_trees(root_value + 1, end)

            # Combine each left and right subtree
            for left_subtree in left_subtrees:
                for right_subtree in right_subtrees:
                    root = TreeNode(value=root_value)
                    root.left = left_subtree
                    root.right = right_subtree
                    all_trees.append(root)

        return all_trees

    # Build BSTs from 1 to number
    return generate_trees(1, number)

Big(O) Analysis

Time Complexity

O(4^n / n^(3/2)) – The algorithm considers each number from 1 to n as the root, recursively generating left and right subtrees. The number of possible binary search trees grows rapidly with n, described by the Catalan number. Catalan numbers, which are approximately 4^n / (n^(3/2) * sqrt(pi)), dictate the complexity. Since we generate all possible trees, the overall time complexity is asymptotically bounded by the nth Catalan number. Constructing the trees from smaller subtrees does not fundamentally change this bound.

Space Complexity

O(N * Catalan(N)) – The space complexity is dominated by the storage of the generated trees. The algorithm constructs all possible unique binary search trees for N nodes. The number of such trees is given by the Catalan number, Catalan(N), which is approximately 4^N / (N * sqrt(N)). Each tree can have up to N nodes, with each node containing references (pointers) to its left and right children. Therefore, the algorithm stores on the order of Catalan(N) trees, and each tree requires O(N) space to store, leading to a space complexity of O(N * Catalan(N)). The recursive call stack also contributes O(N) space in the worst case, but this is less significant than the space required to store the trees themselves.

Optimal Solution

Approach

The problem asks us to generate all possible binary search trees for a given range of numbers. Instead of building each tree individually, we use recursion to break the problem into smaller subproblems and cleverly combine their results. This avoids redundant calculations and builds the trees systematically.

Here's how the algorithm would work step-by-step:

Consider the numbers as a range, for example, from 1 to N.
Pick a number from the range to be the root of a binary search tree.
All numbers smaller than the chosen root will form the left subtree, and all numbers larger will form the right subtree.
Recursively generate all possible left subtrees using the numbers smaller than the root.
Recursively generate all possible right subtrees using the numbers larger than the root.
Combine each possible left subtree with each possible right subtree to create a set of binary search trees with the chosen root.
Repeat this process for every number in the original range to consider each as a potential root.
The final result is a collection of all possible binary search trees for the initial number range.

Code Implementation

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

def generate_trees(number):
    def generate_subtree(start_value, end_value):
        if start_value > end_value:
            return [None]

        all_trees = []
        # Iterate through each number to be the root.
        for index in range(start_value, end_value + 1):
            # Recursively generate all left subtrees.
            all_left_subtrees = generate_subtree(start_value, index - 1)

            # Recursively generate all right subtrees.
            all_right_subtrees = generate_subtree(index + 1, end_value)

            # Combine each left and right subtree.
            for left_subtree in all_left_subtrees:
                for right_subtree in all_right_subtrees:
                    root = TreeNode(index)
                    root.left = left_subtree
                    root.right = right_subtree
                    all_trees.append(root)

        return all_trees

    # Invoke the helper function to generate all trees.
    return generate_subtree(1, number)

Big(O) Analysis

Time Complexity

O(4^n / n^(3/2)) – The algorithm recursively constructs all possible binary search trees for a range of numbers from 1 to n. The dominant factor in the time complexity is the number of possible BSTs, which grows rapidly with n. The number of binary search trees with n nodes is given by the Catalan number, which is approximately 4^n / (n^(3/2) * sqrt(pi)). Constructing each tree takes O(n) time, but the number of trees dwarfs that cost. Therefore, the overall time complexity is asymptotically bounded by the Catalan number, which is O(4^n / n^(3/2)).

Space Complexity

O(N^2) or O(Catalan Number(N)) – The algorithm uses recursion to generate all possible binary search trees. The depth of the recursion can be at most N, where N is the number of nodes. At each level of the recursion, lists of intermediate tree nodes are created to combine left and right subtrees. The number of possible BSTs for N nodes is the Catalan number, which grows faster than exponentially but slower than factorially. Because the number of possible BSTs significantly affects the size of the data stored on call stacks at the worst case, it can also be described as O(N^2). The auxiliary space complexity needed to store the intermediate tree lists at each step will be O(N^2) due to storing intermediate list of the trees and the recursion call stack itself.

Edge Cases

Case	How to Handle
Input n is 0	Return a list containing only 'null' to represent an empty tree or an empty list to represent no trees.
Input n is 1	Return a list containing a single TreeNode with value 1.
Input n is a large value (e.g., > 8)	The number of possible trees grows exponentially, potentially leading to stack overflow or excessive memory usage; memoization is crucial for efficiency.
Negative Input	Input n must be positive, so return an empty list or throw an exception.
Integer overflow with large n	The number of possible trees can become very large; the solution should avoid calculations that might lead to integer overflow.
Recursion depth for large n	The recursive nature of the solution might lead to stack overflow errors for larger 'n'; memoization helps mitigate this by avoiding recomputation of the same subproblems.
Memory constraints with large n	Storing all possible BSTs in a list can consume a significant amount of memory, so optimize the solution to minimize memory usage.
Correctness of tree structure	Ensure generated trees adhere to BST properties: left child <= parent < right child for all nodes.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'n'? Could 'n' be zero or negative?
If 'n' is zero, should I return an empty list, or a list containing a single null node?
Are the BSTs returned expected to be unique in terms of their structure, or just their node values?
Is there a specific order required for the list of BSTs returned?
Will the input 'n' ever be so large that the number of possible trees would cause a memory overflow?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each number as a possible root of the binary search tree.
For each number we pick as the root, separate the remaining numbers into two groups: those smaller (for the left subtree) and those larger (for the right subtree).
Now, for each group of numbers (the smaller ones and the larger ones), repeat the same process: try each number in the group as a root for a subtree, and split the remaining numbers into even smaller left and right groups.
Keep doing this until you have no numbers left. This represents the base case for an empty subtree.
Each time you pick a root and build left and right subtrees, combine them to form a complete binary search tree. Remember that you need to explore all possible combinations of left and right subtrees for a given root.
Store each unique tree you create. Since we are exploring all possibilities, we will generate all valid binary search trees.
Finally, return the collection of all the unique binary search trees you've stored.

Code Implementation

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

def generate_unique_bsts(number):
    if number == 0:
        return []
    
    def generate_trees(start, end):
        if start > end:
            return [None]
        
        all_trees = []
        
        # Iterate through all possible root nodes
        for root_value in range(start, end + 1):
            # Generate all possible left subtrees
            left_subtrees = generate_trees(start, root_value - 1)

            # Generate all possible right subtrees
            right_subtrees = generate_trees(root_value + 1, end)

            # Combine each left and right subtree
            for left_subtree in left_subtrees:
                for right_subtree in right_subtrees:
                    root = TreeNode(value=root_value)
                    root.left = left_subtree
                    root.right = right_subtree
                    all_trees.append(root)

        return all_trees

    # Build BSTs from 1 to number
    return generate_trees(1, number)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the numbers as a range, for example, from 1 to N.
Pick a number from the range to be the root of a binary search tree.
All numbers smaller than the chosen root will form the left subtree, and all numbers larger will form the right subtree.
Recursively generate all possible left subtrees using the numbers smaller than the root.
Recursively generate all possible right subtrees using the numbers larger than the root.
Combine each possible left subtree with each possible right subtree to create a set of binary search trees with the chosen root.
Repeat this process for every number in the original range to consider each as a potential root.
The final result is a collection of all possible binary search trees for the initial number range.

Code Implementation

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

def generate_trees(number):
    def generate_subtree(start_value, end_value):
        if start_value > end_value:
            return [None]

        all_trees = []
        # Iterate through each number to be the root.
        for index in range(start_value, end_value + 1):
            # Recursively generate all left subtrees.
            all_left_subtrees = generate_subtree(start_value, index - 1)

            # Recursively generate all right subtrees.
            all_right_subtrees = generate_subtree(index + 1, end_value)

            # Combine each left and right subtree.
            for left_subtree in all_left_subtrees:
                for right_subtree in all_right_subtrees:
                    root = TreeNode(index)
                    root.left = left_subtree
                    root.right = right_subtree
                    all_trees.append(root)

        return all_trees

    # Invoke the helper function to generate all trees.
    return generate_subtree(1, number)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return a list containing only 'null' to represent an empty tree or an empty list to represent no trees.
Input n is 1	Return a list containing a single TreeNode with value 1.
Input n is a large value (e.g., > 8)	The number of possible trees grows exponentially, potentially leading to stack overflow or excessive memory usage; memoization is crucial for efficiency.
Negative Input	Input n must be positive, so return an empty list or throw an exception.
Integer overflow with large n	The number of possible trees can become very large; the solution should avoid calculations that might lead to integer overflow.
Recursion depth for large n	The recursive nature of the solution might lead to stack overflow errors for larger 'n'; memoization helps mitigate this by avoiding recomputation of the same subproblems.
Memory constraints with large n	Storing all possible BSTs in a list can consume a significant amount of memory, so optimize the solution to minimize memory usage.
Correctness of tree structure	Ensure generated trees adhere to BST properties: left child <= parent < right child for all nodes.