Hello everyone, my name is Fangyuan. I plan to write a special topic on trees, including binary search trees, pre-order, in-order, post-order traversal and red-black trees. I also want to try to see if I can write red-black trees well.
This article is about binary search trees, which is also the basis for all subsequent learning. It will involve pre-order, in-order, and post-order traversals. The subsequent introduction of related traversals will be based on topics. If you want to find the route to solve the problem, you can refer to Github: LeetCode.
Binary search tree
Binary Search Tree (Binary Search Tree) is the basic data structure. When it is a complete binary tree, the time complexity of performing search and insertion is O(logn). However, if the tree is a linear tree made of n nodes, Linked list, then the time complexity of these operations is O(n), which has the following properties:
-
If the left subtree of any node is not empty, then all node values in the left subtree are less than its root node value
-
If the right subtree of any node is not empty, then all node values in the right subtree are greater than its root node value
-
The left subtree is a binary search tree with node values less than the root node; the right subtree is a binary search tree with node values greater than the root node.
Through in-order traversal, we can obtain the ordered sequence of the binary search tree. The template for in-order traversal of the binary tree is as follows:
private void midOrder(TreeNode node) {<!-- -->
if (node == null) {<!-- -->
return;
}
midOrder(node.left);
// do something...
midOrder(node.right);
}
The order of operating nodes in in-order traversal is “Left Root Right”, which happens to be accessed in the order of increasing node values of the binary search tree. Most of the questions related to binary search trees are related to in-order traversal. Let’s look at a few simple questions first:
Note: Generally we will choose the recursive method to solve tree-related questions, but you must not use your head as a computer to simulate the recursive process. We only need to pay attention to the recursive order of the nodes and the “current “The logic done at the node can be
- 1305. All elements in two binary search trees
We can easily solve this problem by using two queues to save the node values in the two binary search trees, and then merge them into the result list according to the size relationship. The solution to the problem is as follows:
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {<!-- -->
LinkedList<Integer> queue1 = new LinkedList<>();
LinkedList<Integer> queue2 = new LinkedList<>();
midOrder(root1, queue1);
midOrder(root2, queue2);
List<Integer> res = new ArrayList<>();
while (!queue1.isEmpty() || !queue2.isEmpty()) {<!-- -->
if (queue1.isEmpty()) {<!-- -->
res.add(queue2.poll());
continue;
}
if (queue2.isEmpty()) {<!-- -->
res.add(queue1.poll());
continue;
}
if (queue1.peek() <= queue2.peek()) {<!-- -->
res.add(queue1.poll());
} else {<!-- -->
res.add(queue2.poll());
}
}
return res;
}
private void midOrder(TreeNode node, Queue<Integer> queue) {<!-- -->
if (node == null) {<!-- -->
return;
}
midOrder(node.left, queue);
queue.offer(node.val);
midOrder(node.right, queue);
}
- LCR 174. Find the target node in the binary search tree
This question is to find the Kth largest node in a binary search tree. We can save all nodes in order through in-order traversal and then return its Kth largest node. The solution to the problem is as follows:
class Solution {<!-- -->
List<Integer> nodes;
public int findTargetNode(TreeNode root, int cnt) {<!-- -->
nodes = new ArrayList<>();
midOrder(root);
return nodes.get(nodes.size() - cnt);
}
private void midOrder(TreeNode node) {<!-- -->
if (node == null) {<!-- -->
return;
}
midOrder(node.left);
nodes.add(node.val);
midOrder(node.right);
}
}
- 230. The Kth smallest element in the binary search tree
Let’s look at another question. This question can also be solved according to the idea of the previous question, but here we introduce a better method: what is required is the Kth small node, then every time the node is passed, K is reduced by one, reduced to When 0 is the node we want, then we can no longer perform recursive searches to avoid subsequent invalid recursion. The solution to the problem is as follows:
class Solution {<!-- -->
int k;
int res;
public int kthSmallest(TreeNode root, int k) {<!-- -->
this.k = k;
midOrder(root);
return res;
}
private void midOrder(TreeNode node) {<!-- -->
if (node == null || k == 0) {<!-- -->
return;
}
midOrder(node.left);
k--;
if (k == 0) {<!-- -->
res = node.val;
return;
}
midOrder(node.right);
}
}
Implementing a binary search tree
Now that we have a basic understanding of the properties of binary search trees, let’s look at how to implement a binary search tree.
Define global variables of Node node class and root root node
public class BinarySearchTree {<!-- -->
static class Node {<!-- -->
int key;
int val;
Node left;
Node right;
public Node(int key, int val) {<!-- -->
this.key = key;
this.val = val;
}
}
// root node
Node root;
}
Query node value
The implementation of the query method is relatively simple. Based on the size relationship of the key values, it can be judged whether to go to the left subtree, the right subtree or return the current node value. The code is as follows:
/**
* Get the corresponding node value based on key
*/
public Integer getValue(int key) {<!-- -->
return getValue(root, key);
}
private Integer getValue(Node node, int key) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (key > node.key) {<!-- -->
return getValue(node.right, key);
}
if (key < node.key) {<!-- -->
return getValue(node.left, key);
}
return node.val;
}
Insert node
The logic implemented by the method of inserting nodes is basically the same as that of the query method, but inserting nodes will change the reference relationship between the parent node and the child node. The first inserted key is the root node, and the second one is inserted. The key will become the left node or the right node of the root node according to the size relationship, and so on. The code is implemented as follows:
/**
* Insert the node into the appropriate position in the binary search tree
*/
public void putNode(int key, int val) {<!-- -->
root = putNode(root, key, val);
}
private Node putNode(Node node, int key, int val) {<!-- -->
if (node == null) {<!-- -->
return new Node(key, val);
}
if (key > node.val) {<!-- -->
node.right = putNode(node.right, key, val);
} else if (key < node.val) {<!-- -->
node.left = putNode(node.left, key, val);
} else {<!-- -->
node.val = val;
}
return node;
}
Get the maximum/minimum node
These two methods are relatively simple. The largest node is the largest node of the right subtree, and the smallest node is the smallest node of the left subtree:
/**
* Get the largest node
*/
public Node getMaxNode() {<!-- -->
if (root == null) {<!-- -->
return null;
}
return getMaxNode(root);
}
private Node getMaxNode(Node node) {<!-- -->
if (node.right == null) {<!-- -->
return node;
}
return getMaxNode(node.right);
}
/**
* Get the smallest node
*/
public Node getMinNode() {<!-- -->
if (root == null) {<!-- -->
return null;
}
return getMinNode(root);
}
private Node getMinNode(Node node) {<!-- -->
if (node.left == null) {<!-- -->
return node;
}
return getMinNode(node.left);
}
Search by rounding down
This method is more interesting. Rounding down is to find the largest node that is less than or equal to the key value. If the given key is less than the value of the root node, then the largest node less than or equal to the key must be in the left subtree; if the given key is greater than the value of the root node, then the largest node less than or equal to the key possibly In the right subtree, when there is no node less than or equal to the key value in the right subtree, the largest node is the root node, otherwise it is a node in the right subtree. The code logic is as follows:
/**
* Round down to find
*/
public Node floor(int key) {<!-- -->
return floor(root, key);
}
private Node floor(Node node, int key) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (key == node.val) {<!-- -->
return node;
}
if (key < node.val) {<!-- -->
return floor(node.left, key);
}
Node right = floor(node.right, key);
return right != null ? right : node;
}
Round up to find
The logic of rounding up is opposite to that of rounding down. We list the code below and think about the specific execution steps:
/**
* Round up to find
*/
public Node ceiling(int key) {<!-- -->
return ceiling(root, key);
}
private Node ceiling(Node node, int key) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (key == node.val) {<!-- -->
return node;
}
if (key > node.val) {<!-- -->
return ceiling(node.right, key);
}
Node left = ceiling(node.left, key);
return left != null ? left : node;
}
Delete node
Deleting nodes is relatively difficult to implement in a binary search tree. Before deleting any node, let’s first write a simple method of deleting the maximum/minimum value node.
Delete the smallest node
To delete the minimum node, we need to find the node whose left subtree is an empty tree. This node is the minimum node we need to delete. After this node is deleted, we need to splice its right subtree to its original position. The implementation is as follows:
/**
* Delete the smallest node
*/
public void deleteMin() {<!-- -->
root = deleteMin(root);
}
private Node deleteMin(Node node) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (node.left == null) {<!-- -->
return node.right;
}
node.left = deleteMin(root.left);
return node;
}
Delete the largest node
This implementation is completely similar to the logic of deleting the smallest node, as follows:
/**
* Delete the largest node
*/
public void deleteMax() {<!-- -->
root = deleteMax(root);
}
private Node deleteMax(Node node) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (node.right == null) {<!-- -->
return node.left;
}
node.right = deleteMax(node.right);
return node;
}
Delete the specified node
To delete a node with a specified key value, we need to find the node first, and then discuss it on a case-by-case basis:
-
If the left subtree of the node is empty, then the right subtree of the node needs to be spliced to the position of the deleted node;
-
If the right subtree of the node is empty, then the left subtree of the node needs to be spliced to the position of the deleted node;
-
The first two cases are similar to when we delete the most valuable node. The third case is that the left and right subtrees of the node are not empty. Then we can find the minimum node of the right subtree of the node and splice the left subtree of the node to On the left subtree of the minimum node (Similarly, we can also find the maximum node of the left subtree of the node, and then splice the right subtree of the node to the right subtree of the maximum node), the implementation is as follows:
/**
* Delete the specified node
*/
public void delete(int key) {<!-- -->
root = delete(key, root);
}
private Node delete(int key, Node node) {<!-- -->
if (node == null) {<!-- -->
return null;
}
if (key > node.val) {<!-- -->
node.right = delete(key, node.right);
return node;
}
if (key < node.val) {<!-- -->
node.left = delete(key, node.left);
return node;
}
if (node.left == null) {<!-- -->
return node.right;
}
if (node.right == null) {<!-- -->
return node.left;
}
Node min = getMinNode(node.right);
min.left = node.left;
return node;
}
Range search
The implementation of range search in binary search trees is very simple. It only needs to be traversed in order according to the size condition relationship. The implementation is as follows:
/**
* Range search
*
* @param left lower bound of interval
* @param right upper bound of interval
*/
public List<Integer> keys(int left, int right) {<!-- -->
ArrayList<Integer> res = new ArrayList<>();
keys(root, left, right, res);
return res;
}
private void keys(Node node, int left, int right, ArrayList<Integer> res) {<!-- -->
if (node == null) {<!-- -->
return;
}
if (node.val > left) {<!-- -->
keys(node.left, left, right, res);
}
if (node.val >= left & amp; & amp; node.val <= right) {<!-- -->
res.add(node.val);
}
if (node.val < right) {<!-- -->
keys(node.right, left, right, res);
}
}
In general, the implementation of binary search trees is not difficult. It is best for everyone to implement these methods for better learning and understanding.
Related exercises
Now that we are familiar with binary search trees and in-order traversal, let’s do some questions to check. We have already said in the previous article that the general binary search tree questions will most likely be related to in-order traversal. In addition, when performing in-order traversal, some questions require us to record the “predecessor node” of the node. to help solve the problem, this needs to be noted.
- 235. Recent common ancestor of binary search tree
To find the nearest common ancestor on the binary search tree, we will discuss it according to the situation: if the values of both nodes are smaller than the current node, then go to the left subtree to find; if the values of both nodes are larger than the current node, then go to the right subtree Tree search; if any one of the two nodes is equal to the current node or the two nodes are greater or less than the current node, then the current node is the nearest common ancestor (you can draw a picture to see it). The solution to the problem is as follows:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {<!-- -->
if (p.val < root.val & amp; & amp; q.val < root.val) {<!-- -->
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > root.val & amp; & amp; q.val > root.val) {<!-- -->
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
- 450. Delete nodes in binary search tree
This question is logically consistent with the method of deleting nodes in the binary search tree mentioned above, except that here we obtain the minimum node of the right subtree through iteration. The solution to the question is as follows:
public TreeNode deleteNode(TreeNode root, int key) {<!-- -->
if (root == null) {<!-- -->
return null;
}
if (key > root.val) {<!-- -->
root.right = deleteNode(root.right, key);
return root;
}
if (key < root.val) {<!-- -->
root.left = deleteNode(root.left, key);
return root;
}
if (root.right == null) {<!-- -->
return root.left;
}
if (root.left == null) {<!-- -->
return root.right;
}
TreeNode rightNode = root.right;
while (rightNode.left != null) {<!-- -->
rightNode = rightNode.left;
}
rightNode.left = root.left;
return root.right;
}
- 669. Pruning Binary Search Tree
This problem also relies on the properties of binary search trees to solve:
-
If the current node value is smaller than low, then it needs to be pruned and go to its right subtree to find a node that satisfies the interval condition;
-
If the current node value is larger than high, then it also needs to be pruned, and its left subtree is searched to find a node that satisfies the interval condition;
-
If the current node value is within the interval, you need to prune its left subtree and right subtree, and return the current node. The solution to the problem is as follows:
public TreeNode trimBST(TreeNode root, int low, int high) {<!-- -->
if (root == null) {<!-- -->
return null;
}
if (root.val < low) {<!-- -->
return trimBST(root.right, low, high);
}
if (root.val > high) {<!-- -->
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
- 98. Verify binary search tree
The binary search tree needs to satisfy the properties that the root node is greater than any node in the left subtree and the root node is less than any node in the right subtree. We can verify based on this condition. It should be noted that we need to record the predecessor node to help compare the nodes. The size relationship, the solution is as follows:
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {<!-- -->
if (root == null) {<!-- -->
return true;
}
boolean left = isValidBST(root.left);
if (pre >= root.val) {<!-- -->
return false;
}
pre = root.val;
boolean right = isValidBST(root.right);
return left & amp; & amp; right;
}
- LCR 155. Convert a binary search tree into a sorted doubly linked list
Just splice the linked list according to the order of in-order traversal. You can create sentinel nodes for the precursor nodes to reduce the empty judgment logic. The solution to the problem is as follows:
Node pre = null;
public Node treeToDoublyList(Node root) {<!-- -->
if (root == null) {<!-- -->
return null;
}
Node head = new Node();
pre = head;
midOrder(root);
head.right.left = pre;
pre.right = head.right;
return head.right;
}
private void midOrder(Node node) {<!-- -->
if (node == null) {<!-- -->
return;
}
midOrder(node.left);
pre.right = node;
node.left = pre;
pre = node;
midOrder(node.right);
}
- 99. Restore binary search tree
The idea of solving this problem is not complicated. It is determined that two nodes have been exchanged, so we can mark them with two pointers. The solution is as follows:
TreeNode one = null, two = null;
TreeNode pre;
public void recoverTree(TreeNode root) {<!-- -->
midOrder(root);
int temp = one.val;
one.val = two.val;
two.val = temp;
}
private void midOrder(TreeNode node) {<!-- -->
if (node == null) {<!-- -->
return;
}
midOrder(node.left);
if (pre != null & amp; & amp; pre.val > node.val) {<!-- -->
if (one == null) {<!-- -->
one = pre;
}
two = node;
}
pre = node;
midOrder(node.right);
}
- Interview Question 04.06. Successor
Find the successor node of the specified node. If the predecessor node is the specified node, then the current node is the desired successor node. The solution to the problem is as follows:
TreeNode pre = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {<!-- -->
if (root == null) {<!-- -->
return null;
}
TreeNode left = inorderSuccessor(root.left, p);
if (pre != null & amp; & amp; pre.val == p.val) {<!-- -->
pre = root;
return root;
}
pre = root;
TreeNode right = inorderSuccessor(root.right, p);
return left == null ? right : left;
}
Giant’s Shoulders
-
Wikipedia – Binary search tree
-
“Hello Algorithm”: Chapter 7.4 Binary Search Tree
-
“Algorithms, Fourth Edition”: Chapter 3.2 Binary Search Tree
-
“Introduction to Algorithms, Third Edition”: Chapter 12 Binary Search Tree