Introduction

When working with a sorted integer array, you might wonder how many unique Binary Search Trees (BSTs) can be constructed from it. The characteristics of a Binary Search Tree — where the left subtree of a node contains only nodes with values less than the node's value, and the right subtree only nodes with values greater — ties deeply into this consideration.

Technical Explanation

For a given sorted integer array, the question of how many distinct BSTs can be formed is solved by understanding Catalan numbers. To figure this out, it's essential to delve into combinatorial structures and dynamic programming.

Catalan Numbers

Catalan numbers provide the precise solution to finding the number of distinct BSTs for a sorted array. The $n^{th}$ Catalan number $C_n$ can be calculated using the formula:

$$C_n = \frac{1}{{n+1}}\binom{{2n}}{n} = \frac{{(2n)!}}{{(n+1)!n!}}$$

In terms of BSTs for a sorted array with $n$ distinct elements, the number of unique trees that can be formed is equivalently the $n^{th}$ Catalan number, $C_n$.

Recursive Approach

To construct a BST from a sorted array, consider choosing any element as the root. Then, the elements to its left form the left subtree, and those to its right form the right subtree. This division is recursive:

1. Choose the $i$-th element as the root.
2. Form the left subtree with elements from index $0$ to $(i-1)$.
3. Form the right subtree with elements from $(i+1)$ to the end.

Mathematically, for an array of length $n$:

$$T(n) = \sum_{i=1}^{n} T(i-1) \times T(n-i)$$

where $T(n)$ represents the number of unique BSTs formed with $n$ nodes, and base case $T(0) = T(1) = 1$. This is the recursive definition of Catalan numbers as it applies to binary trees.

Example

Consider the array `[1, 2, 3]`. The number of unique BSTs that can be formed is given by:

1. Choosing 1 as root: • Left subtree: None • Right subtree: Nodes [2, 3]
2. Choosing 2 as root: • Left subtree: Node [1] • Right subtree: Node [3]
3. Choosing 3 as root: • Left subtree: Nodes [1, 2] • Right subtree: None

Computing this using our recursive approach:

• For root 1: sum of 1 (for left) * 2 (for right) = 2 trees • For root 2: sum of 1 (for left) * 1 (for right) = 1 tree • For root 3: sum of 2 (for left) * 1 (for right) = 2 trees

Thus, total = 2 + 1 + 2 = 5 distinct BSTs.

Computational Complexity

The formula using Catalan numbers allows for efficient computation of the number of trees. The recursion can be implemented using dynamic programming, which runs in $O(n^2)$ for computing values up to $C_n$. Moreover, since $n$ is typically small in practical applications (due to factorial growth), this remains computationally feasible.

Tableau Summary

Conclusion

The exploration into the number of unique Binary Search Trees (BSTs) that can be formed from a sorted integer array not only provides a fascinating peek into combinatorial mathematics but also underscores the power of Catalan numbers in solving recursive tree-related problems. By employing recursive structures and leveraging dynamic programming, one can efficiently calculate the number of different BSTs that can be constructed from sorted arrays for practical or theoretical applications.