Binary Search Tree in Action (Basic Operations)
This article will resolve
LeetCode | Difficulty |
---|---|
450. Delete Node in a BST | 🟠 |
700. Search in a Binary Search Tree | 🟢 |
701. Insert into a Binary Search Tree | 🟠 |
98. Validate Binary Search Tree | 🟠 |
Prerequisite
Before reading this article, you should first learn:
In the previous article Binary Search Tree Basics (Features), we introduced the basic features of BST and used the "in-order traversal is sorted" property to solve some problems. In this article, we'll implement the basic operations of BST: checking if a BST is valid, inserting, deleting, and searching. Among these, "deleting" and "checking validity" are a bit more complex.
The basic operations of BST mainly rely on the "left smaller, right bigger" property. This allows us to do binary search-like operations in the tree, making it very efficient to find an element. For example, the following is a valid binary search tree:

For BST problems, you will often see code logic like this:
void BST(TreeNode root, int target) {
if (root.val == target)
// found the target, do something
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}
void BST(TreeNode* root, int target) {
if (root->val == target)
// found the target, do something
if (root->val < target)
BST(root->right, target);
if (root->val > target)
BST(root->left, target);
}
def BST(root: TreeNode, target: int) -> None:
if root.val == target:
# target found, do something
if root.val < target:
BST(root.right, target)
if root.val > target:
BST(root.left, target)
func BST(root *TreeNode, target int) {
if root.Val == target {
// found the target, do something
}
if root.Val < target {
BST(root.Right, target)
}
if root.Val > target {
BST(root.Left, target)
}
}
var BST = function(root, target) {
if (root.val === target) {
// found the target, do something
}
if (root.val < target) {
BST(root.right, target);
}
if (root.val > target) {
BST(root.left, target);
}
};
This code framework is similar to the usual binary tree traversal, just using the BST "left smaller, right bigger" feature. Next, let's see how the basic operations on BST are implemented.
1. Check if a BST is Valid
LeetCode Problem 98 "Validate Binary Search Tree" asks you to check if a given BST is valid:
98. Validate Binary Search Tree | LeetCode | 🟠
Given the root
of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- 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 = [2,1,3] Output: true
Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. -231 <= Node.val <= 231 - 1
Be careful, there is a trap here. According to the BST property, every node should be compared with its left and right children to check if it is valid. It seems you might write code like this:
boolean isValidBST(TreeNode root) {
if (root == null) return true;
// the left side of the root should be smaller
if (root.left != null && root.left.val >= root.val)
return false;
// the right side of the root should be larger
if (root.right != null && root.right.val <= root.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
// the left side of root should be smaller
if (root->left != nullptr && root->left->val >= root->val)
return false;
// the right side of root should be bigger
if (root->right != nullptr && root->right->val <= root->val)
return false;
return isValidBST(root->left)
&& isValidBST(root->right);
}
def isValidBST(root: TreeNode) -> bool:
if root is None:
return True
# the left of root should be smaller
if root.left is not None and root.left.val >= root.val:
return False
# the right of root should be larger
if root.right is not None and root.right.val <= root.val:
return False
return isValidBST(root.left) and isValidBST(root.right)
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
// the left side of root should be smaller
if root.Left != nil && root.Left.Val >= root.Val {
return false
}
// the right side of root should be larger
if root.Right != nil && root.Right.Val <= root.Val {
return false
}
return isValidBST(root.Left)
&& isValidBST(root.Right)
}
var isValidBST = function(root) {
if (root === null) return true;
// the left side of the root should be smaller
if (root.left !== null && root.left.val >= root.val)
return false;
// the right side of the root should be larger
if (root.right !== null && root.right.val <= root.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
But this algorithm is wrong. For BST, every node must be less than all nodes in its right subtree. The following tree is not a valid BST because there is a node 8
in the left subtree of node 7
, but our code would say it is valid:
The reason for the mistake is that, for each node root
, the code only checks its left and right child nodes. But, by the definition of BST, the whole left subtree of root
must be less than root.val
, and the whole right subtree must be greater than root.val
.
The problem is, for a node root
, it can only directly check its children. How do we pass this constraint down to all nodes of the left and right subtree? Here is the correct code:
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
// nodes in the subtree rooted at root must satisfy max.val > root.val > min.val
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// if root.val does not satisfy the constraints of max and min, it is not a valid BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// the maximum value in the left subtree is root.val, and
// the minimum value in the right subtree is root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
}
class Solution {
public:
bool isValidBST(TreeNode* root) {
return _isValidBST(root, nullptr, nullptr);
}
// Definition: This function returns whether all nodes in the
// subtree rooted at root satisfy max->val > root->val > min->val
bool _isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
// base case
if (root == nullptr) return true;
// If root->val does not satisfy the constraints of max and min, it is not a valid BST
if (min != nullptr && root->val <= min->val) return false;
if (max != nullptr && root->val >= max->val) return false;
// According to the definition, the maximum value of the left subtree is
// root->val and the minimum value of the right subtree is root->val
return _isValidBST(root->left, min, root)
&& _isValidBST(root->right, root, max);
}
};
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
return self._isValidBST(root, None, None)
# Definition: This function returns whether all nodes in the
# subtree rooted at `root` satisfy max.val > root.val > min.val
def _isValidBST(self, root: TreeNode, min: TreeNode, max: TreeNode) -> bool:
# base case
if root is None:
return True
# If root.val does not comply with the constraints of max and min, it is not a valid BST
if min is not None and root.val <= min.val:
return False
if max is not None and root.val >= max.val:
return False
# According to the definition, the maximum value of the left subtree is
# root.val, and the minimum value of the right subtree is root.val
return self._isValidBST(root.left, min, root) and self._isValidBST(root.right, root, max)
func isValidBST(root *TreeNode) bool {
return _isValidBST(root, nil, nil)
}
// Definition: This function returns whether all nodes of the
// subtree rooted at root satisfy max.Val > root.Val > min.Val
func _isValidBST(root *TreeNode, min, max *TreeNode) bool {
// base case
if root == nil {
return true
}
// If root.Val does not meet the constraints of max and min, it is not a valid BST
if min != nil && root.Val <= min.Val {
return false
}
if max != nil && root.Val >= max.Val {
return false
}
// By definition, limit the maximum value of the left subtree to
// root.Val and the minimum value of the right subtree to root.Val
return _isValidBST(root.Left, min, root) && _isValidBST(root.Right, root, max)
}
var isValidBST = function(root) {
return _isValidBST(root, null, null);
};
// Definition: This function returns whether all nodes in the
// subtree rooted at 'root' satisfy max.val > root.val > min.val
var _isValidBST = function(root, min, max) {
// base case
if (root === null) return true;
// If root.val does not meet the constraints of max and min, it is not a valid BST
if (min !== null && root.val <= min.val) return false;
if (max !== null && root.val >= max.val) return false;
// According to the definition, the maximum value of the left subtree is
// root.val, and the minimum value of the right subtree is root.val
return _isValidBST(root.left, min, root)
&& _isValidBST(root.right, root, max);
};
Algorithm Visualization
We use a helper function and add extra parameters to pass down these constraints to all child nodes. This is also a useful trick in binary tree algorithms.
Search for an Element in a BST
LeetCode problem 700, "Search in a Binary Search Tree," asks you to find a node with value target
in a BST. The function signature is as follows:
TreeNode searchBST(TreeNode root, int target);
TreeNode* searchBST(TreeNode* root, int target);
def searchBST(root: TreeNode, target: int) -> TreeNode:
func searchBST(root *TreeNode, target int) *TreeNode {
// Implementation goes here
}
var searchBST = function(root, target) {}
If you are searching in a normal binary tree, you can write the code like this:
TreeNode searchBST(TreeNode root, int target) {
if (root == null) return null;
if (root.val == target) return root;
// if the current node is not found, recursively search the left and right subtrees
TreeNode left = searchBST(root.left, target);
TreeNode right = searchBST(root.right, target);
return left != null ? left : right;
}
TreeNode* searchBST(TreeNode* root, int target) {
if (root == nullptr) return nullptr;
if (root->val == target) return root;
// if the current node is not found, recursively search the left and right subtrees
TreeNode* left = searchBST(root->left, target);
TreeNode* right = searchBST(root->right, target);
return left != nullptr ? left : right;
}
def searchBST(root, target):
if not root:
return None
if root.val == target:
return root
# if the current node is not found, recursively search the left and right subtrees
left = searchBST(root.left, target)
right = searchBST(root.right, target)
return left if left else right
func searchBST(root *TreeNode, target int) *TreeNode {
if root == nil {
return nil
}
if root.val == target {
return root
}
// recursively search left and right subtrees
left := searchBST(root.left, target)
right := searchBST(root.right, target)
// if the target node is found in the left subtree, return
// the left subtree; otherwise, return the right subtree
if left != nil {
return left
}
return right
}
var searchBST = function(root, target) {
if (root == null) return null;
if (root.val == target) return root;
// if the current node is not found, recursively search the left and right subtrees
let left = searchBST(root.left, target);
let right = searchBST(root.right, target);
return left != null ? left : right;
};
This code is correct, but it checks all nodes, which is brute-force and works for any binary tree. But how can we use the special property of BST, where the left side is smaller and the right side is larger?
It is simple. You do not need to search both sides. You can use a binary search idea: compare target
with root.val
. This way, you can ignore one side. Let's change the code using this idea:
// define: search for the node with value target in the BST rooted at root, return the node
TreeNode searchBST(TreeNode root, int target) {
if (root == null) {
return null;
}
// search in the left subtree
if (root.val > target) {
return searchBST(root.left, target);
}
// search in the right subtree
if (root.val < target) {
return searchBST(root.right, target);
}
// the current node is the target value
return root;
}
// define: search for the node with value target in the BST rooted at root, return the node
TreeNode* searchBST(TreeNode* root, int target) {
if (root == nullptr) {
return nullptr;
}
// search in the left subtree
if (root->val > target) {
return searchBST(root->left, target);
}
// search in the right subtree
if (root->val < target) {
return searchBST(root->right, target);
}
// the current node is the target value
return root;
}
# define: search for the node with value target in the BST rooted at root, return the node
def searchBST(root: TreeNode, target: int) -> TreeNode:
# if the binary tree is empty, return directly
if not root:
return None
# search in the left subtree
if root.val > target:
return searchBST(root.left, target)
# search in the right subtree
if root.val < target:
return searchBST(root.right, target)
# the current node is the target value
return root
// define: search for the node with value target in the BST rooted at root, return the node
func searchBST(root *TreeNode, target int) *TreeNode {
// if the root node is nil, return nil
if root == nil {
return nil
}
// search in the left subtree
if root.val > target {
return searchBST(root.left, target)
}
// search in the right subtree
if root.val < target {
return searchBST(root.right, target)
}
// the current node is the target value
return root
}
// define: search for the node with value target in the BST rooted at root, return the node
var searchBST = function(root,target) {
if (root === null) {
return null;
}
// search in the left subtree
if (root.val > target) {
return searchBST(root.left, target);
}
// search in the right subtree
if (root.val < target) {
return searchBST(root.right, target);
}
// target value equals the current node, return directly
return root;
}
Algorithm Visualization
Insert a Number into a BST
When working with data structures, you usually travel through (find) and visit (change) the nodes. For this problem, to insert a number, you first find the right position, then insert it.
BSTs usually do not have duplicate values, so you do not need to insert a value that is already in the BST. The code below assumes you will not insert a value that already exists in the BST.
In the last problem, we summarized the way to travel through a BST, which is the "find" part. Now, just add the "change" part.
If you need to change the tree, it is like building a binary tree; the function should return TreeNode
, and you need to use the result from the recursive call.
LeetCode problem 701, "Insert into a Binary Search Tree," is about this:
701. Insert into a Binary Search Tree | LeetCode | 🟠
You are given the root
node of a binary search tree (BST) and a value
to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:

Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:![]()
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5]
Constraints:
- The number of nodes in the tree will be in the range
[0, 104]
. -108 <= Node.val <= 108
- All the values
Node.val
are unique. -108 <= val <= 108
- It's guaranteed that
val
does not exist in the original BST.
Let's look at the solution code. You can use the comments and visual panel to help you understand:
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
// find the empty spot to insert the new node
if (root == null) return new TreeNode(val);
// if (root.val == val)
// generally, in a bst, we don't insert an element that already exists
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
}
// define: insert val into the BST rooted at root, return the root of the modified BST
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
// find the empty position to insert the new node
return new TreeNode(val);
}
// look for the insertion position in the right subtree
if (root->val < val) {
root->right = insertIntoBST(root->right, val);
}
// look for the insertion position in the left subtree
if (root->val > val) {
root->left = insertIntoBST(root->left, val);
}
// return root, the upper recursion will take the return value as a child node
return root;
}
};
# define: insert val into the BST rooted at root, return the root of the modified BST
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
# find an empty spot to insert the new node
return TreeNode(val)
# go to the right subtree to find the insertion position
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
# go to the left subtree to find the insertion position
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
# return root, the upper level of recursion will
# receive the return value as a child node
return root
// define: insert val into the BST rooted at root, return the root of the modified BST
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
// find the empty position to insert the new node
return &TreeNode{Val: val}
}
// find the position to insert in the right subtree
if root.Val < val {
root.Right = insertIntoBST(root.Right, val)
}
// find the position to insert in the left subtree
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
}
// return root, the upper recursion will receive the return value as a child node
return root
}
// define: insert val into the BST rooted at root, return the root of the modified BST
var insertIntoBST = function(root, val) {
if (root === null) {
// find the empty spot to insert the new node
return new TreeNode(val);
}
// find the insertion spot in the right subtree
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
}
// find the insertion spot in the left subtree
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
}
// return root, the upper recursion will receive the return value as a child node
return root;
}
Algorithm Visualization
3. Delete a Node in a BST
LeetCode Problem 450: Delete Node in a BST asks you to delete a node with value key
from a BST:
450. Delete Node in a BST | LeetCode | 🟠
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.![]()
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0 Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. -105 <= Node.val <= 105
- Each node has a unique value.
root
is a valid binary search tree.-105 <= key <= 105
Follow up: Could you solve it with time complexity O(height of tree)
?
This problem is a bit tricky. Like insertion, you need to "find" first, then "change." Let's write the basic structure first:
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// found it, proceed to delete
} else if (root.val > key) {
// go to the left subtree
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// go to the right subtree
root.right = deleteNode(root.right, key);
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (root->val == key) {
// found it, proceed to delete
} else if (root->val > key) {
// go to the left subtree
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
// go to the right subtree
root->right = deleteNode(root->right, key);
}
return root;
}
def deleteNode(root: TreeNode, key: int) -> TreeNode:
if root.val == key:
# Found it, proceed with deletion
elif root.val > key:
# Search in the left subtree
root.left = deleteNode(root.left, key)
elif root.val < key:
# Search in the right subtree
root.right = deleteNode(root.right, key)
return root
func deleteNode(root *TreeNode, key int) *TreeNode {
if root.Val == key {
// found it, proceed to delete
} else if root.Val > key {
// look in the left subtree
root.Left = deleteNode(root.Left, key)
} else if root.Val < key {
// look in the right subtree
root.Right = deleteNode(root.Right, key)
}
return root
}
var deleteNode = function(root, key) {
if (root.val === key) {
// Found it, proceed with deletion
} else if (root.val > key) {
// Go to the left subtree to search
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// Go to the right subtree to search
root.right = deleteNode(root.right, key);
}
return root;
}
After finding the target node, let's say it is node A
, how do we delete it? This is the main challenge, because you can't break the properties of the BST. There are three possible cases, shown with pictures.
Case 1: A
is a leaf node (both children are null). You can simply delete it.

if (root.left == null && root.right == null)
return null;
Case 2: A
has only one non-empty child. Let this child take A
's place.

// After excluding case 1
if (root.left == null) return root.right;
if (root.right == null) return root.left;
Case 3: A
has two children. This is more complex. To keep the BST property, you must find either the largest node in the left subtree or the smallest node in the right subtree to replace A
. We will explain the second way.

if (root.left != null && root.right != null) {
// Find the smallest node in the right subtree
TreeNode minNode = getMin(root.right);
// Replace root with minNode
root.val = minNode.val;
// Delete minNode
root.right = deleteNode(root.right, minNode.val);
}
After explaining all three cases, fill them into the framework and simplify the code:
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// these two if statements correctly handle cases 1 and 2
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// handle case 3
// get the smallest node in the right subtree
TreeNode minNode = getMin(root.right);
// delete the smallest node in the right subtree
root.right = deleteNode(root.right, minNode.val);
// replace the root node with the smallest node from the right subtree
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
TreeNode getMin(TreeNode node) {
// the leftmost node in a BST is the smallest
while (node.left != null) node = node.left;
return node;
}
}
class Solution {
public:
// define: delete the node with value key in the BST
// rooted at root, return the root after deletion
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
if (root->val == key) {
// these two if statements correctly handle cases 1 and 2
if (root->left == nullptr) return root->right;
if (root->right == nullptr) return root->left;
// handle case 3
// get the smallest node in the right subtree
TreeNode* minNode = getMin(root->right);
// delete the smallest node in the right subtree
root->right = deleteNode(root->right, minNode->val);
// replace the root node with the smallest node in the right subtree
minNode->left = root->left;
minNode->right = root->right;
root = minNode;
} else if (root->val > key) {
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
}
return root;
}
TreeNode* getMin(TreeNode* node) {
// in a BST, the leftmost node is the smallest
while (node->left != nullptr) node = node->left;
return node;
}
};
class Solution:
# define: delete the node with value key in the BST
# rooted at root, return the root after deletion
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if root == None:
return None
if root.val == key:
# These two if statements correctly handle cases 1 and 2
if root.left == None:
return root.right
if root.right == None:
return root.left
# handle case 3
# get the smallest node in the right subtree
minNode = self.getMin(root.right)
# delete the smallest node in the right subtree
root.right = self.deleteNode(root.right, minNode.val)
# replace the root node with the smallest node in the right subtree
minNode.left = root.left
minNode.right = root.right
root = minNode
elif root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
return root
def getMin(self, node: TreeNode) -> TreeNode:
# The leftmost node in a BST is the smallest
while node.left != None:
node = node.left
return node
// define: delete the node with value key in the BST
// rooted at root, return the root after deletion
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if root.Val == key {
// these two if statements correctly handle cases 1 and 2
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
// handle case 3
// get the smallest node in the right subtree
minNode := getMin(root.Right)
// delete the smallest node in the right subtree
root.Right = deleteNode(root.Right, minNode.Val)
// replace the root node with the smallest node in the right subtree
minNode.Left = root.Left
minNode.Right = root.Right
root = minNode
} else if root.Val > key {
root.Left = deleteNode(root.Left, key)
} else if root.Val < key {
root.Right = deleteNode(root.Right, key)
}
return root
}
// get the smallest node in the binary search tree
func getMin(node *TreeNode) *TreeNode {
// the leftmost node in a BST is the smallest
for node.Left != nil {
node = node.Left
}
return node
}
// define: delete the node with value key in the BST
// rooted at root, return the root after deletion
var deleteNode = function(root, key) {
if (root == null) return null;
if (root.val == key) {
// These two if-statements handle cases 1 and 2 correctly
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// handle case 3
// get the smallest node in the right subtree
let minNode = getMin(root.right);
// delete the smallest node in the right subtree
root.right = deleteNode(root.right, minNode.val);
// replace the root node with the smallest node in the right subtree
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
// get the smallest node in the BST.
var getMin = function(node) {
// the leftmost node in the BST is the smallest
while (node.left != null) node = node.left;
return node;
}
Algorithm Visualization
Now, the delete operation is finished. Note: In case 3, the code above replaces the root
node with minNode
by swapping their values, which is a bit simpler:
// Handle case 3
// Get the smallest node in the right subtree
TreeNode minNode = getMin(root.right);
// Delete the smallest node in the right subtree
root.right = deleteNode(root.right, minNode.val);
// Replace root node with the smallest node in the right subtree
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
Some readers may wonder why we need to swap the nodes with pointer operations. Why not just change the val
field? It looks easier:
// Handle case 3
// Get the smallest node in the right subtree
TreeNode minNode = getMin(root.right);
// Delete the smallest node in the right subtree
root.right = deleteNode(root.right, minNode.val);
// Replace root node with the smallest node in the right subtree
root.val = minNode.val;
For this algorithm problem, it is fine. But in real applications, we do not swap nodes by just changing the internal value. The data inside a BST node could be very complex, and the BST structure should not care about the actual data. So, we prefer using pointers to swap nodes.
Let's summarize a few key points from this article:
- If the current node will affect its children, you can pass information by adding parameters to helper functions.
- Master how to insert, delete, search, and update nodes in a BST.
- When changing a data structure with recursion, always receive the return value and return the updated node.
That's all for this article. For more classic binary tree problems and recursion practice, see the Recursion Practice for Binary Search Trees in the binary tree chapter.