Binary Search Tree in Action (Construction)
Info
English content is still improving...
You will not only learn the algorithm tricks, also resolve these LeetCode problems:
LeetCode | Difficulty |
---|---|
95. Unique Binary Search Trees II | 🟠 |
96. Unique Binary Search Trees | 🟠 |
Prerequisites
Before reading this article, you should first learn:
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 enumeration problem. So, what method can correctly enumerate the number of valid BSTs?
As we mentioned earlier, don't underestimate "exhaustive enumeration." It seems simple, but it requires some technical skill. The key issue is to ensure you don't miss any possibilities or count too many. So, how do you do it?
In the previous Step-by-Step Binary Tree Series Part 1, we talked about the key to binary tree algorithms: clearly defining what the root node needs to do. Since a BST is a special kind of binary tree, the core idea is the same.