Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Introduction

A binary tree is a hierarchical data structure in which each node has at most two children. Also, a binary search tree (BST) is a more specific type of binary tree where the main characteristic is that it’s sorted. Therefore, a binary tree is a BST if and only if an in-order traversal of the binary tree results in a sorted sequence.

This tutorial will show how to compute the number of binary search trees based on the number of tree nodes.

2. Unique Number of Binary Search Trees

In a BST, each node contains a sortable key. For example, we can label each node with an integer number. Therefore, the key in each node of a BST is greater than or equal to any key stored in the left subtree and less than or equal to any key stored in the right subtree.

Given a list of n distinct numbers, we are interested in computing the number of BSTs labeled by these numbers. Without the loss of generality, we can assume the numbers are 1, 2, 3, ..., n. For example, there are 5 possible binary search trees for 1, 2, 3:

unique bst

Although it is easy to enumerate all possible tree structures when n is small, the number of unique BST structures increases very fast when n gets bigger. For example, there are 16796 unique BST structures when n=10. Therefore, we need to compute this number with an algorithm. In this tutorial, we’ll show different approaches to compute this number.

3. Recursive Approach

Let f(n) denote the total number of unique BST structures for number n. For a list of n unique numbers, we can choose any number as the root. For example, we can choose the number i (i\in[1,n]) as the root. Then, numbers in [1, i-1] will be in the left subtree. Also, numbers in [i+1, n] will be in the right subtree.

Since we have (i-1) numbers in the left subtree, the left subtree has f(i-1) unique BST structures. Similarly, the right subtree has f(n-i) unique tree structures. Also, the arrangements in the left and right subtrees are independent. Therefore, we have a total of f(i-1) \times f(n-i) unique tree structures when i is the root.

Since we have n possible ways to choose the root, we can add together f(i-1) \times f(n-i) for all possible values of i:

Rendered by QuickLaTeX.com

If we don’t have any nodes in one subtree, then we’ll only consider the total number of unique tree structures in the other subtree. Therefore, the base case of the formula is f(0) = 1.

As a result, we can construct a recursive algorithm based on the above formula:

Rendered by QuickLaTeX.com

4. Dynamic Programming Approach

In general, the recursive algorithm is straightforward based on the recursive formula. However, it has many repeat computations. To avoid that, we can use a dynamic programming approach to compute the number.

We can first compute f(n) with smaller numbers and store the results into an array. Then, when we compute bigger numbers, we can reuse the previously computed results from the smaller numbers:

Rendered by QuickLaTeX.com

In this algorithm, we use a loop to compute our number step by step. For a number f(i), we use another loop to compute its value based on our recursive formula.

For example, our base case is f(0) = 1. Then, we compute f(1) based on the value of f(0). After that, the next step is to compute f(2) based on the values of f(0) and f(1).

We repeat this process for each number from 1 to n. Therefore, when we compute f(i), all the required values for the computation are already available. Eventually, we’ll compute f(n) and return this value.

Since we have a nested loop to do the computation, the overall time complexity of this algorithm is O(n^2).

5. Catalan Number Approach

The number of different BSTs is actually a Catalan Number:

Rendered by QuickLaTeX.com

Therefore, we can compute our number f(n) directly from the Catalan Number. However, we need to compute 3 factorial numbers based on this formula.

To avoid the time consuming factorial computations, we can also use the following recurrence property of Catalan Number in our algorithm:

Rendered by QuickLaTeX.com

As a result, the algorithm based on this recurrence is:

Rendered by QuickLaTeX.com

Since we use only one loop to do the computation, the overall running time is O(n).

6. Conclusion

This tutorial showed a recursive formula to compute the number of unique binary search trees with n nodes. Also, we provided several approaches to compute this number. As a result, the Catalan Number approach is the fastest algorithm among them to compute this number. However, the dynamic programming approach is more intuitive as it directly comes from the analysis of BST structures.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!