Binary Search Tree in Action (Construction)

Previously, I wrote two articles on practicing BST algorithm problems step-by-step. The first article discussed the significance of in-order traversal for BSTs, and the second article covered basic BST operations.

This article is the third in the step-by-step BST series, progressively explaining two problems on how to calculate all valid BSTs.

The first problem is LeetCode Problem 96 "Unique Binary Search Trees". Given a positive integer n, calculate the number of different BST structures that can be formed with values {1, 2, 3, ..., n}.

The function signature is as follows:

int numTrees(int n);

int numTrees(int n);

def numTrees(n: int) -> int:

func numTrees(n int) int {}

var numTrees = function(n) {

};

For example, if the input is n = 3, the algorithm returns 5 because there are 5 different BST structures that can store {1,2,3}:

This is a classic exhaustive problem. So, how can we correctly enumerate the number of valid BSTs?

As mentioned earlier, do not underestimate "exhaustive enumeration." It appears simple but requires technical skill. The key to the problem is ensuring that you neither miss nor count any structures incorrectly. How do you achieve this?

In the previous Binary Tree Algorithms Tutorial Part 1, it was stated that the key to binary tree algorithms is determining what the root node needs to do. The core idea is the same for a BST, which is a special type of binary tree.