Generating Unique Binary Search Trees

Given an integer n, the problem asks us to find the total number of structurally unique Binary Search Trees (BSTs) that can be constructed using values from 1 to n. Understanding this helps in analyzing tree structures and their variations, which is fundamental in data structures and algorithms.

Problem Description

A Binary Search Tree (BST) is a binary tree data structure with the following properties:

• The left subtree of a node contains only nodes with keys greater than the node’s key.
• The right subtree of a node contains only nodes with keys less than the node’s key.
• Both the left and right subtrees must also be binary search trees.

We are given an integer n. We need to construct all possible structurally unique Binary Search Trees using nodes with values ranging from 1 to n. The goal is to return the total count of these unique BSTs.

Key Requirements:

• The trees must be structurally unique, meaning the arrangement of nodes matters.
• The values used for nodes are precisely the integers from 1 to n.

Expected Behavior: For a given n, calculate and return the total number of distinct BSTs that can be formed.

Edge Cases:

• n = 0: If n is 0, there are no nodes, and thus only one way to form an empty tree.
• n = 1: With one node, there's only one possible BST.

Examples

Example 1:

Input: n = 3
Output: 5
Explanation: The following are the 5 unique BSTs for n = 3:

       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

Example 2:

Input: n = 1
Output: 1
Explanation: For n = 1, there is only one node (value 1), resulting in a single BST.

Example 3:

Input: n = 0
Output: 1
Explanation: For n = 0, there are no nodes, and an empty tree is considered a valid BST.

Constraints

• 0 <= n <= 19
• n is an integer.
• The solution should aim for an efficient time complexity, ideally polynomial.

Notes

Consider how the choice of the root node affects the structure of the left and right subtrees. This problem has a classic dynamic programming or recursive structure. Think about how to break down the problem for n nodes into subproblems involving fewer nodes.