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

Unique Binary Search Trees II

Number: 95

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Apple, Uber

Problem Description

Given an integer n, generate all structurally unique binary search trees (BSTs) that store values 1 to n. Each BST must have exactly n nodes where each node value is unique from 1 to n.

Key Insights

  • Utilize a recursive (divide and conquer) approach where each number in the range can be chosen as the root.
  • For a chosen root, all numbers less than the root become part of the left subtree, and all numbers greater become part of the right subtree.
  • Recursively generate all valid left and right subtrees then combine them to form unique BSTs.
  • Base case: When the starting index exceeds the ending index, return a list containing None (or null in other languages) to represent an empty tree.
  • The problem essentially generates trees corresponding to Catalan numbers.

Space and Time Complexity

Time Complexity: O(n * Catalan(n))
Space Complexity: O(n * Catalan(n)) (space used to store all generated trees and recursion stack)

Solution

We use a recursive function that accepts a range (start, end) and returns all possible BSTs constructed from numbers within that range. For every possible root value within the range, we recursively generate all possible left subtrees (from start to value-1) and right subtrees (from value+1 to end). We then iterate over every combination of left and right subtree and create a new tree node with the selected root value. This tree is appended to our list of unique BSTs. Key details include handling the base case where the start index exceeds the end index (which represents an empty subtree) and combining results appropriately.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # Initialize the node's value
        self.left = left     # Reference to the left subtree
        self.right = right   # Reference to the right subtree

class Solution:
    def generateTrees(self, n: int):
        # Edge-case: if no numbers, return empty list
        if n == 0:
            return []

        # Recursive helper function to generate BSTs for a given range
        def generate_trees(start, end):
            trees = []
            # Base case: represent an empty tree
            if start > end:
                trees.append(None)
                return trees
            # Loop through each number as a potential root
            for root_val in range(start, end + 1):
                # All possible left subtrees if root_val is chosen
                left_trees = generate_trees(start, root_val - 1)
                # All possible right subtrees if root_val is chosen
                right_trees = generate_trees(root_val + 1, end)
                # Combine each left and right subtree with the root
                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(root_val)
                        root.left = left
                        root.right = right
                        trees.append(root)
            return trees

        return generate_trees(1, n)
        
# Example usage:
# sol = Solution()
# trees = sol.generateTrees(3)
# This will generate all unique BSTs for n = 3.
← Back to All Questions