# 二叉搜索树心法（特性篇）

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

1038. Binary Search Tree to Greater Sum Tree | 🟠 |

230. Kth Smallest Element in a BST | 🟠 |

538. Convert BST to Greater Tree | 🟠 |

Prerequisites

Before reading this article, you should learn:

In previous articles, we have walked you through binary trees with Mindset Series, Construction Series, Postorder Series, and Serialization Series.

Today, we start a series on Binary Search Trees (BST, for short) and guide you through solving BST problems step by step.

First, you should be familiar with the characteristics of BST (detailed in the basic knowledge section of Basic Binary Tree Structure):

For every node

`node`

in a BST, the values of the nodes in the left subtree are smaller than`node`

, and the values of the nodes in the right subtree are larger than`node`

.For every node

`node`

in a BST, both its left and right subtrees are also BSTs.

Binary search trees are not complicated, but I believe they are half of the data structure world. Data structures directly based on BST include AVL trees, red-black trees, etc., which have self-balancing properties and can provide logN efficiency for insertions, deletions, and searches. Other structures like B+ trees and segment trees are also designed based on the BST concept.

**From the perspective of solving algorithm problems, besides its definition, BST has an important property: the inorder traversal of a BST results in a sorted (ascending) sequence**.

This means that if you are given a BST, the following code can print the values of each node in ascending order:

```
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// inorder traversal code position
print(root.val);
traverse(root.right);
}
```

```
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
traverse(root->left);
// in-order traversal code position
print(root->val);
traverse(root->right);
}
```

```
def traverse(root):
if not root:
return
traverse(root.left)
# in-order traversal code position
print(root.val)
traverse(root.right)
```

```
func traverse(root *TreeNode) {
if root == nil {
return
}
traverse(root.left)
// inorder traversal code position
fmt.Println(root.val)
traverse(root.right)
}
```

```
var traverse = function(root) {
if (root === null) return;
traverse(root.left);
// inorder traversal code position
console.log(root.val);
traverse(root.right);
};
```

Based on this property, let's solve two algorithm problems.

## Finding the Kth Smallest Element

This is LeetCode problem 230, "Kth Smallest Element in a BST." Let's look at the problem:

**230. Kth Smallest Element in a BST** | 力扣 | LeetCode |

Given the `root`

of a binary search tree, and an integer `k`

, return *the* `k`

^{th}*smallest value ( 1-indexed) of all the values of the nodes in the tree*.

**Example 1:**

Input:root = [3,1,4,null,2], k = 1Output:1

**Example 2:**

Input:root = [5,3,6,2,4,null,null,1], k = 3Output:3

**Constraints:**

- The number of nodes in the tree is
`n`

. `1 <= k <= n <= 10`

^{4}`0 <= Node.val <= 10`

^{4}

**Follow up:** If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

This requirement is quite common. A straightforward approach is to sort the elements in ascending order and then find the `k`

th element. The inorder traversal of a BST essentially gives us the sorted order, so finding the `k`

th element should be straightforward.

Following this approach, we can directly write the code:

```
class Solution {
int kthSmallest(TreeNode root, int k) {
// Utilize the in-order traversal property of BST
traverse(root, k);
return res;
}
// Record the result
int res = 0;
// Record the rank of the current element
int rank = 0;
void traverse(TreeNode root, int k) {
if (root == null) {
return;
}
traverse(root.left, k);
// In-order traversal code position
rank++;
if (k == rank) {
// Found the kth smallest element
res = root.val;
return;
}
traverse(root.right, k);
}
}
```

```
class Solution {
private:
// record the result
int res = 0;
// record the rank of the current element
int rank = 0;
void traverse(TreeNode* root, int k) {
if (root == nullptr) {
return;
}
traverse(root->left, k);
// inorder traversal code position
rank++;
if (k == rank) {
// found the kth smallest element
res = root->val;
return;
}
traverse(root->right, k);
}
public:
int kthSmallest(TreeNode* root, int k) {
// utilize the inorder traversal property of BST
traverse(root, k);
return res;
}
};
```

```
class Solution:
def __init__(self):
# record the result
self.res = 0
# record the rank of the current element
self.rank = 0
def kthSmallest(self, root: TreeNode, k: int) -> int:
# utilize the in-order traversal characteristic of BST
self.traverse(root, k)
return self.res
def traverse(self, root, k):
if not root:
return
self.traverse(root.left, k)
# in-order traversal code position
self.rank += 1
if k == self.rank:
# found the kth smallest element
self.res = root.val
return
self.traverse(root.right, k)
```

```
func kthSmallest(root *TreeNode, k int) int {
// record the result
res := 0
// record the rank of the current element
rank := 0
var traverse func(root *TreeNode)
traverse = func(root *TreeNode) {
if root == nil {
return
}
traverse(root.Left)
// inorder traversal code position
rank++
if k == rank {
// found the kth smallest element
res = root.Val
return
}
traverse(root.Right)
}
// utilize the inorder traversal property of BST
traverse(root)
return res
}
```

```
var kthSmallest = function(root, k) {
// record the result
let res = 0;
// record the rank of the current element
let rank = 0;
var traverse = function(root) {
if (root === null) {
return;
}
traverse(root.left);
// in-order traversal code position
rank++;
if (k === rank) {
// found the kth smallest element
res = root.val;
return;
}
traverse(root.right);
}
// utilize the in-order traversal property of BST
traverse(root);
return res;
}
```

We've finished this problem, but let's talk a bit more. This solution is not the most efficient; it's just specific to this problem.

In our previous article Efficiently Calculating the Median of a Data Stream, we mentioned today's problem:

相关信息

If you were to implement a method `select(int k)`

to find an element in a binary search tree (BST) by its rank, how would you design it?

Using the method we just discussed, which leverages the property that "in-order traversal of a BST results in a sorted sequence," finding the k-th smallest element would require an in-order traversal each time. The worst-case time complexity is `O(N)`

, where `N`

is the number of nodes in the BST.

Remember, BST properties are very powerful. For example, a self-balancing BST like a Red-Black Tree has `O(logN)`

complexity for insertions, deletions, and searches. Calculating the k-th smallest element with a time complexity of `O(N)`

seems inefficient.

Ideally, the best algorithm for finding the k-th smallest element should also have a logarithmic complexity, but this depends on how much information each BST node records.

Why are BST operations so efficient? Take searching for an element as an example. The root cause of BST's ability to find an element in logarithmic time lies in its definition: left subtree values are smaller, and right subtree values are larger. Each node can decide whether to search in the left or right subtree by comparing its value, thus avoiding a full tree traversal and achieving logarithmic complexity.

So, for this problem, to find the k-th smallest element, or the element with rank k, achieving logarithmic complexity hinges on each node knowing its own rank.

For instance, if you ask me to find the element with rank k, and the current node knows it has rank m, I can compare m and k:

- If
`m == k`

, I've found the k-th element, so I return the current node. - If
`k < m`

, the k-th element is in the left subtree, so I search for the k-th element there. - If
`k > m`

, the k-th element is in the right subtree, so I search for the (k - m - 1)-th element there.

This approach reduces the time complexity to `O(logN)`

.

So, how can each node know its rank?

As we mentioned earlier, we need to maintain additional information in the binary tree nodes. **Each node needs to record the number of nodes in the subtree rooted at itself**.

In other words, the fields in our `TreeNode`

should look like this:

```
class TreeNode {
int val;
// total number of nodes in the tree rooted at this node
int size;
TreeNode left;
TreeNode right;
}
```

```
class TreeNode {
public:
int val;
// total number of nodes in the tree rooted at this node
int size;
TreeNode* left;
TreeNode* right;
};
```

```
class TreeNode:
def __init__(self):
self.val = None
# total number of nodes in the tree rooted at this node
self.size = None
self.left = None
self.right = None
```

```
type TreeNode struct {
Val int
// total number of nodes in the tree rooted at this node
Size int
Left *TreeNode
Right *TreeNode
}
```

```
function TreeNode() {
var val;
// total number of nodes in the tree rooted at this node
var size;
var left;
var right;
}
```

With the `size`

field and the property of BST nodes where the left child is smaller and the right child is larger, we can derive the rank of each node `node`

through `node.left`

, achieving the logarithmic-time algorithm we mentioned earlier.

Of course, the `size`

field needs to be correctly maintained when adding or deleting elements. The `TreeNode`

provided by LeetCode does not have a `size`

field, so for this problem, we can only use the in-order traversal property of BST. However, the optimization approach mentioned above is a common operation in BST and is still necessary to understand.

## Converting BST to Greater Tree

LeetCode problems 538 and 1038 are the same as this one, so you can solve them together. Here is the problem statement:

**538. Convert BST to Greater Tree** | 力扣 | LeetCode |

Given the `root`

of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a *binary search tree* is a tree that satisfies these constraints:

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

**Example 1:**

Input:root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]Output:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

**Example 2:**

Input:root = [0,null,1]Output:[1,null,1]

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 10`

.^{4}] `-10`

^{4}<= Node.val <= 10^{4}- All the values in the tree are
**unique**. `root`

is guaranteed to be a valid binary search tree.

**Note:** This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

The problem should be easy to understand. For example, for the node 5 in the diagram, when converted to a greater tree, the nodes greater than 5 are 6, 7, and 8. Adding 5 itself, the value of this node in the greater tree should be 5+6+7+8=26.

We need to convert the BST into a greater tree. The function signature is as follows:

`TreeNode convertBST(TreeNode root)`

`TreeNode* convertBST(TreeNode* root);`

`def convertBST(root: TreeNode) -> TreeNode:`

`func convertBST(root *TreeNode) *TreeNode {}`

`var convertBST = function(root) {}`

Following the general approach for binary trees, we need to think about what each node should do. However, for this problem, it's hard to come up with a clear strategy.

In a Binary Search Tree (BST), each node has smaller values on the left and larger values on the right. This seems like useful information. Since the cumulative sum is the total of all elements greater than or equal to the current value, can't we just calculate the sum of the right subtree for each node?

This won't work. For a given node, it's true that all elements in the right subtree are larger, but the parent node might also be larger. We can't be sure because we don't have a pointer to the parent node. So, the general binary tree approach doesn't apply here.

**Since this path is blocked, let's try a different approach, still leveraging the in-order traversal property of BSTs**.

Earlier, we mentioned that the in-order traversal of a BST prints node values in ascending order. But what if we want to print the values in descending order?

It's simple. Just change the order of recursion: traverse the right subtree first, then the left subtree:

```
void traverse(TreeNode root) {
if (root == null) return;
// First, recursively traverse the right subtree
traverse(root.right);
// Inorder traversal code position
print(root.val);
// Then, recursively traverse the left subtree
traverse(root.left);
}
```

```
void traverse(TreeNode* root) {
if (root == nullptr) return;
// first recursively traverse the right subtree
traverse(root->right);
// in-order traversal code position
print(root->val);
// then recursively traverse the left subtree
traverse(root->left);
}
```

```
def traverse(root):
if root is None:
return
# first recursively traverse the right subtree
traverse(root.right)
# inorder traversal code position
print(root.val)
# then recursively traverse the left subtree
traverse(root.left)
```

```
func traverse(root *TreeNode) {
if root == nil {
return
}
// first recursively traverse the right subtree
traverse(root.Right)
// inorder traversal code position
fmt.Println(root.Val)
// then recursively traverse the left subtree
traverse(root.Left)
}
```

```
var traverse = function(root) {
if (root == null) return;
// First recursively traverse the right subtree
traverse(root.right);
// In-order traversal code position
console.log(root.val);
// Then recursively traverse the left subtree
traverse(root.left);
}
```

**This code can print the values of BST nodes in descending order. If we maintain an external cumulative variable sum, and then assign sum to each node in the BST, wouldn't that convert the BST into a cumulative tree**?

Take a look at the code to understand:

```
class Solution {
TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
// record the cumulative sum
int sum = 0;
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
// maintain the cumulative sum
sum += root.val;
// convert BST to cumulative tree
root.val = sum;
traverse(root.left);
}
}
```

```
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
traverse(root);
return root;
}
private:
// record the cumulative sum
int sum = 0;
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
traverse(root->right);
// maintain the cumulative sum
sum += root->val;
// convert BST to accumulation tree
root->val = sum;
traverse(root->left);
}
};
```

```
class Solution:
def __init__(self):
# record the cumulative sum
self.sum = 0
def convertBST(self, root):
self.traverse(root)
return root
def traverse(self, root):
if root is None:
return
self.traverse(root.right)
# maintain the cumulative sum
self.sum += root.val
# convert BST to cumulative tree
root.val = self.sum
self.traverse(root.left)
```

```
func convertBST(root *TreeNode) *TreeNode {
// record the cumulative sum
sum := 0
// define a closure for traverse
traverse := func(root *TreeNode) {}
traverse = func(root *TreeNode) {
if root == nil {
return
}
traverse(root.Right)
// maintain the cumulative sum
sum += root.Val
// convert BST to a cumulative tree
root.Val = sum
traverse(root.Left)
}
traverse(root)
return root
}
```

```
var convertBST = function(root){
var sum = 0;
var traverse = function(root) {
if (root == null) {
return;
}
traverse(root.right);
// maintain the cumulative sum
sum += root.val;
// convert BST to cumulative tree
root.val = sum;
traverse(root.left);
}
traverse(root);
return root;
}
```

This problem is solved by leveraging the in-order traversal property of BST (Binary Search Tree). We simply modified the recursive order to traverse the BST in descending order, aligning with the requirements of the cumulative tree problem.

To summarize briefly, BST-related problems either utilize the BST property of smaller values on the left and larger on the right to enhance algorithm efficiency, or use the in-order traversal property to meet specific problem requirements. That's pretty much it.

This article ends here. For more classic binary tree exercises and recursive thinking training, please refer to the Exercise Section in the binary tree chapter.