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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Binary Search Trees II

Difficulty: Medium

Problem Description

Given an integer n, return all the structurally unique BSTs (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Key Insights

  • Each number from 1 to n can serve as the root of the BST.
  • The numbers to the left of the root must be less than the root, and the numbers to the right must be greater.
  • We can use recursion to generate all possible left and right subtrees for each root.
  • The unique structures can be built by combining the left and right subtrees for each choice of root.

Space and Time Complexity

Time Complexity: O(4^n / sqrt(n)) - This is because the number of unique BSTs grows exponentially with n. Space Complexity: O(n) - This is the space used by the recursion stack.

Solution

To solve the problem, we will use a recursive backtracking approach. The algorithm involves the following steps:

  1. Define a recursive function that generates BSTs for a given range of values.
  2. For each value in the range, consider it as the root of the BST.
  3. Recursively generate all possible left subtrees using values less than the root.
  4. Recursively generate all possible right subtrees using values greater than the root.
  5. Combine each left and right subtree with the current root to form unique BSTs.
  6. Return the list of generated BSTs.

The main data structures used are lists to hold the generated trees and a tree node structure for representing the BST.

Code Solutions

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

def generateTrees(n):
    if n == 0:
        return []
    
    def generate_trees(start, end):
        if start > end:
            return [None]
        
        all_trees = []
        for i in range(start, end + 1):
            # Generate all left and right subtrees
            left_trees = generate_trees(start, i - 1)
            right_trees = generate_trees(i + 1, end)
            
            # Combine left and right trees with the root i
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    all_trees.append(root)
        
        return all_trees
    
    return generate_trees(1, n)
← Back to All Questions