deepSWE.io

Unique Binary Search Trees II

TreesDynamic Programming

Problem Statement

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

Example

Algorithm Explanation

This problem is a follow-up to "Unique Binary Search Trees". Instead of just counting the trees, we need to generate all of them. We can use a recursive approach.

Algorithm Steps

Recursive Function: We'll create a recursive function that takes a start and end value and returns a list of all unique BSTs that can be formed with values in that range.
Base Case: If `start > end`, it means we have an empty subtree, so we return a list containing `null`.
Iterate and Recurse: We iterate from `start` to `end`. For each number `i` in this range, we treat it as the root. We then make recursive calls to generate all possible left subtrees (from `start` to `i-1`) and all possible right subtrees (from `i+1` to `end`).
Combine Subtrees: We then combine each left subtree with each right subtree to form all possible trees with `i` as the root.

Start

Generating unique BSTs for n = 3

Unique Binary Search Trees II Solution


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n == 0:
            return []
        return self._generate_trees(1, n)

    def _generate_trees(self, start, end):
        if start > end:
            return [None]
        
        all_trees = []
        for i in range(start, end + 1):
            left_trees = self._generate_trees(start, i - 1)
            right_trees = self._generate_trees(i + 1, end)
            
            for l in left_trees:
                for r in right_trees:
                    current_tree = TreeNode(i)
                    current_tree.left = l
                    current_tree.right = r
                    all_trees.append(current_tree)
                    
        return all_trees