Common algorithms for working with Binary Search Trees (BSTs)
Here’s a list of common algorithms for working with Binary Search Trees (BSTs), each with a simple explanation of the main principles followed by a Java example.
1. Insertion in a BST
Principle
Inserting a node into a BST follows the binary search property: for each node, values less than the node go to the left subtree, and values greater go to the right subtree. Recursively, starting from the root, the function moves left or right until it finds a null position where the new node should be inserted.
Example
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public TreeNode insert(TreeNode root, int key) {
if (root == null) return new TreeNode(key);
if (key < root.val) {
root.left = insert(root.left, key);
} else if (key > root.val) {
root.right = insert(root.right, key);
}
return root;
}
2. Searching in a BST
Principle
To search for a value in a BST, compare it with the root node. If it matches, the search is successful. If the value is smaller, search the left subtree; if larger, search the right subtree. Continue recursively until you find the value or reach a null node.
Example
public boolean search(TreeNode root, int key) {
if (root == null) return false;
if (root.val == key) return true;
return key < root.val ? search(root.left, key) : search(root.right, key);
}
3. Deletion in a BST
Principle
Deleting a node in a BST has three cases:
1. Leaf node (no children): Remove the node directly.
2. One child: Replace the node with its child.
3. Two children: Find the node’s in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree) and replace the node with it, then delete the successor or predecessor node.
Example
public TreeNode delete(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = delete(root.left, key);
} else if (key > root.val) {
root.right = delete(root.right, key);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = delete(root.right, minNode.val);
}
return root;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
4. In-Order Traversal
Principle
In-order traversal visits nodes in ascending order for a BST (left, root, right). It first traverses the left subtree, then visits the root node, and finally traverses the right subtree.
Example
public void inOrder(TreeNode root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
5. Pre-Order Traversal
Principle
Pre-order traversal (root, left, right) visits the root node first, then the left subtree, and finally the right subtree. It is commonly used for copying or serializing the tree.
Example
public void preOrder(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
}
6. Post-Order Traversal
Principle
Post-order traversal (left, right, root) visits the left subtree first, then the right subtree, and finally the root node. It’s used for deleting or freeing nodes in a tree.
Example
public void postOrder(TreeNode root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}
7. Finding the Minimum and Maximum Value
Principle
The minimum value in a BST is located at the leftmost node, while the maximum value is at the rightmost node. Follow the left or right pointers until reaching a node without further left or right children.
Example
public int findMin(TreeNode root) {
while (root.left != null) root = root.left;
return root.val;
}
public int findMax(TreeNode root) {
while (root.right != null) root = root.right;
return root.val;
}
8. Finding the Height of the BST
Principle
The height of a BST is the longest path from the root to a leaf. Recursively calculate the height of each subtree, and add 1 for each level, choosing the maximum height between left and right subtrees.
Example
public int height(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
9. Checking if a Tree is a BST
Principle
To verify if a tree is a BST, recursively ensure each node’s value falls within a valid range. The left subtree should contain values less than the current node, and the right subtree should contain values greater.
Example
public boolean isBST(TreeNode root) {
return isBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBSTHelper(TreeNode node, int min, int max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return isBSTHelper(node.left, min, node.val) && isBSTHelper(node.right, node.val, max);
}
10. Finding the Lowest Common Ancestor (LCA)
Principle
For two nodes in a BST, the Lowest Common Ancestor (LCA) is the first node that has both target nodes in different subtrees (or is one of the target nodes). Move left or right depending on the values until finding the node where one target node is in the left subtree and the other in the right subtree.
Example
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
Each of these algorithms uses recursive and iterative techniques to work with binary search trees efficiently, maintaining the order and properties of BSTs.
0