Skip to content
The Chat Archive
o1-mini-2024-09-12· OpenAI WildChat-4.8M (AI2)

Given an integer n, return all the structurally unique BST's (binary search trees),…

  1. User

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

  2. Assistant

    To solve the problem of generating all structurally unique Binary Search Trees (BSTs) with n nodes containing unique values from 1 to n, we can use a recursive approach. The idea is to consider each number in the range as the root of the BST, and then recursively generate all possible left and right subtrees.

    Here's a step-by-step explanation and a Python implementation of the solution:

    Step-by-Step Explanation

    1. Understanding BST Properties:

      • In a BST, for any given node with value val, all nodes in the left subtree have values less than val, and all nodes in the right subtree have values greater than val.
    2. Recursive Generation:

      • Base Case: If start > end, there's no number to construct the subtree, so we return [None] indicating an empty subtree.
      • Recursive Case:
        • Iterate through each number i from start to end and consider it as the root.
        • Recursively generate all possible left subtrees using the numbers less than i.
        • Recursively generate all possible right subtrees using the numbers greater than i.
        • Combine each left and right subtree with the current root i to form a new BST.
    3. Combining Trees:

      • For each possible root, combine every left subtree with every right subtree to form all unique BSTs rooted at that number.
    4. Final Output:

      • The recursion builds up all possible trees, and the final result is a list of all unique BSTs.

    Python Implementation

    Below is the Python code implementing the above approach. It uses a helper function generate to recursively build the trees. The TreeNode class represents each node in the BST.

    from typing import List, Optional
    from dataclasses import dataclass
    
    # Definition for a binary tree node.
    @dataclass
    class TreeNode:
        val: int
        left: Optional['TreeNode'] = None
        right: Optional['TreeNode'] = None
    
    class Solution:
        def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
            if n == 0:
                return []
            
            def generate(start: int, end: int) -> List[Optional[TreeNode]]:
                trees = []
                if start > end:
                    trees.append(None)
                    return trees
                
                # Iterate through all values as the root
                for root_val in range(start, end + 1):
                    # Generate all possible left subtrees
                    left_trees = generate(start, root_val - 1)
                    # Generate all possible right subtrees
                    right_trees = generate(root_val + 1, end)
                    
                    # Combine left and right subtrees with the current 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(1, n)
    
    # Example Usage:
    # To print all unique BSTs for n = 3, you can use the following code:
    def print_tree(node: Optional[TreeNode], prefix: str = ""):
        if not node:
            print(prefix + "None")
            return
        print(prefix + f"TreeNode({node.val})")
        if node.left or node.right:
            print_tree(node.left, prefix + "  L--")
            print_tree(node.right, prefix + "  R--")
    
    if __name__ == "__main__":
        sol = Solution()
        all_trees = sol.generateTrees(3)
        for idx, tree in enumerate(all_trees, 1):
            print(f"Tree {idx}:")
            print_tree(tree)
            print("-" * 20)
    

    Explanation of the Example Usage

    The print_tree function is a helper to visualize the BSTs generated for n = 3. When you run the code, it will print all 5 unique BSTs that can be constructed with values from 1 to 3.

    Complexity Analysis

    • Time Complexity: The number of unique BSTs with n nodes is given by the n-th Catalan number, which is approximately (O(4^n / n^{3/2})). Generating all trees involves constructing each unique structure, leading to similar exponential time complexity.
    • Space Complexity: The space complexity is also proportional to the number of unique BSTs, which is exponential in n.

    Conclusion

    This recursive approach efficiently generates all structurally unique BSTs by leveraging the properties of BSTs and systematically combining possible left and right subtrees for each potential root. The provided Python implementation can be used directly or adapted to other programming languages as needed.