5-Binary Search Trees (BSTs)¶
Binary search trees use the concepts underpinning the binary search algorithm to create a dynamic data structure. This makes them a blend of the efficiency of binary search with the adaptability of dynamic data structures.
Trees are hierarchical data structures composed of branching nodes. Each tree node may have two child pointers, forming a binary structure.
A node contains a value and up to two child pointers:
TreeNode { Type: value TreeNode: left TreeNode: right TreeNode: parent }Nodes with at least one child are called internal nodes. Nodes with no children are leaf nodes.
A binary search tree (BST) starts at a single root node and branches downward. Programs access the BST through a single pointer to the root.
For any node
N:
All values in the left subtree of
Nare less thanN.value.All values in the right subtree of
Nare greater thanN.value.This ordering effectively keeps the tree sorted.
By default, BSTs assume unique values. Handling duplicates requires modifying the property.
Searching a BST¶
Searching begins at the root. At each node:
If
target < node.value→ go leftIf
target > node.value→ go rightIf
target == node.value→ successRecursive search pseudocode:
FindValue(TreeNode: current, Type: target): IF current == null: return null IF current.value == target: return current IF target < current.value AND current.left != null: return FindValue(current.left, target) IF target > current.value AND current.right != null: return FindValue(current.right, target) return nullIterative version:
FindValueItr(TreeNode: root, Type: target): TreeNode: current = root WHILE current != null AND current.value != target: IF target < current.value: current = current.left ELSE: current = current.right return currentComplexity is proportional to the depth of the target value.
Sorted arrays: binary search gives logarithmic lookup, but insertions and deletions are expensive.
Binary search trees: slightly more overhead, but dynamic updates are efficient.
Thus, BSTs shine in dynamic environments where data changes frequently.
Adding Nodes¶
Insertion follows the same path as search until a dead end is reached:
InsertTreeNode(BinarySearchTree: tree, Type: new_value): IF tree.root == null: tree.root = TreeNode(new_value) ELSE: InsertNode(tree.root, new_value) InsertNode(TreeNode: current, Type: new_value): IF new_value == current.value: Update node as needed return IF new_value < current.value: IF current.left != null: InsertNode(current.left, new_value) ELSE: current.left = TreeNode(new_value) current.left.parent = current ELSE: IF current.right != null: InsertNode(current.right, new_value) ELSE: current.right = TreeNode(new_value) current.right.parent = currentComplexity: proportional to the depth of the insertion path.
Removing Nodes¶
Three cases exist:
Leaf node – Delete directly and update parent.
Node with one child – Promote the child to take its place.
Node with two children – Replace node with its successor
(the leftmost node in the right subtree).
RemoveTreeNode(BinarySearchTree: tree, TreeNode: node): IF tree.root == null OR node == null: return # Case A: Leaf node IF node.left == null AND node.right == null: # Case B: One child IF node.left == null OR node.right == null: # Case C: Two children successor = node.right WHILE successor.left != null: successor = successor.left RemoveTreeNode(tree, successor)Complexity: proportional to tree depth.
Balanced vs. Unbalanced Trees¶
Balanced BSTs: operations scale as
O(log N).Unbalanced BSTs: can degrade to
O(N), resembling a linked list.Balanced trees (like AVL or Red-Black trees) solve this problem by enforcing balance rules.
#include <iostream>
using namespace std;
// A node of the Binary Search Tree
struct Node {
int key; // The data (or "key") stored in the node
Node* left; // Pointer to left child
Node* right; // Pointer to right child
// Constructor to create a new node easily
Node(int value) {
key = value;
left = right = nullptr;
}
};
// Binary Search Tree class
class BST {
private:
Node* root; // Root of the tree
// Helper function to insert a key recursively
Node* insert(Node* node, int key) {
// If tree is empty, create a new node
if (node == nullptr) {
return new Node(key);
}
// If the key is smaller, go to the left subtree
if (key < node->key) {
node->left = insert(node->left, key);
}
// If the key is larger, go to the right subtree
else if (key > node->key) {
node->right = insert(node->right, key);
}
// If key == node->key, we don’t insert duplicates in a BST
return node; // Return the (unchanged) node pointer
}
// Helper function to search for a key recursively
bool search(Node* node, int key) {
if (node == nullptr) return false; // Key not found
if (node->key == key) return true; // Key found
if (key < node->key) return search(node->left, key); // Search left
return search(node->right, key); // Search right
}
// Helper function to find the minimum value node in a subtree
Node* findMin(Node* node) {
while (node && node->left != nullptr) {
node = node->left;
}
return node;
}
// Helper function to delete a key recursively
Node* remove(Node* node, int key) {
if (node == nullptr) return node; // Key not found
if (key < node->key) {
node->left = remove(node->left, key); // Go left
}
else if (key > node->key) {
node->right = remove(node->right, key); // Go right
}
else {
// Node found
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp; // Replace with right child
}
else if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp; // Replace with left child
}
// Node with two children: get the inorder successor (smallest in the right subtree)
Node* temp = findMin(node->right);
// Copy inorder successor's value to this node
node->key = temp->key;
// Delete the inorder successor
node->right = remove(node->right, temp->key);
}
return node;
}
// Helper function for in-order traversal (Left, Root, Right)
void inorder(Node* node) {
if (node == nullptr) return;
inorder(node->left);
cout << node->key << " ";
inorder(node->right);
}
public:
// Constructor initializes an empty tree
BST() {
root = nullptr;
}
// Public wrapper functions call private recursive helpers
void insert(int key) {
root = insert(root, key);
}
void remove(int key) {
root = remove(root, key);
}
bool search(int key) {
return search(root, key);
}
void inorder() {
inorder(root);
cout << endl;
}
};
// Driver code to test BST
int main() {
BST tree;
// Insert elements into BST
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
cout << "In-order traversal of the BST: ";
tree.inorder(); // Should print: 20 30 40 50 60 70 80
cout << "Searching for 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
cout << "Searching for 90: " << (tree.search(90) ? "Found" : "Not Found") << endl;
cout << "Deleting 20\n";
tree.remove(20);
tree.inorder();
cout << "Deleting 30\n";
tree.remove(30);
tree.inorder();
cout << "Deleting 50\n";
tree.remove(50);
tree.inorder();
return 0;
}
# Binary Search Tree implementation in Python
# Each node stores:
# - data (the key value)
# - left child (smaller values)
# - right child (larger values)
class Node:
"""Represents a single node in the Binary Search Tree."""
def __init__(self, key):
self.key = key # The value stored in this node
self.left = None # Pointer to the left child node
self.right = None # Pointer to the right child node
class BinarySearchTree:
"""Binary Search Tree (BST) implementation."""
def __init__(self):
self.root = None # The root node of the tree
# -------------------------
# INSERTION
# -------------------------
def insert(self, key):
"""Insert a new key into the BST."""
if self.root is None:
# If the tree is empty, the new node becomes the root
self.root = Node(key)
else:
# Otherwise, recursively insert into the tree
self._insert_recursive(self.root, key)
def _insert_recursive(self, current_node, key):
"""Helper method to recursively find the correct spot for insertion."""
if key < current_node.key:
# If the new key is smaller, go left
if current_node.left is None:
current_node.left = Node(key) # Insert here
else:
self._insert_recursive(current_node.left, key)
elif key > current_node.key:
# If the new key is larger, go right
if current_node.right is None:
current_node.right = Node(key) # Insert here
else:
self._insert_recursive(current_node.right, key)
else:
# If the key already exists, do nothing (no duplicates)
pass
# -------------------------
# SEARCH
# -------------------------
def search(self, key):
"""Search for a key in the BST. Returns True if found, else False."""
return self._search_recursive(self.root, key)
def _search_recursive(self, current_node, key):
"""Helper method for recursive search."""
if current_node is None:
return False # Reached the end, not found
if current_node.key == key:
return True # Found the key
elif key < current_node.key:
return self._search_recursive(current_node.left, key) # Search left
else:
return self._search_recursive(current_node.right, key) # Search right
# -------------------------
# INORDER TRAVERSAL
# -------------------------
def inorder_traversal(self):
"""Return a list of all keys in ascending order (inorder traversal)."""
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, current_node, result):
"""Helper method for recursive inorder traversal."""
if current_node is not None:
self._inorder_recursive(current_node.left, result) # Visit left subtree
result.append(current_node.key) # Visit the current node
self._inorder_recursive(current_node.right, result) # Visit right subtree
# -------------------------
# DELETE
# -------------------------
def delete(self, key):
"""Delete a key from the BST if it exists."""
self.root = self._delete_recursive(self.root, key)
def _delete_recursive(self, current_node, key):
"""Helper method for recursive delete."""
if current_node is None:
return current_node # Base case: key not found
# Step 1: Search for the node
if key < current_node.key:
current_node.left = self._delete_recursive(current_node.left, key)
elif key > current_node.key:
current_node.right = self._delete_recursive(current_node.right, key)
else:
# Found the node to be deleted
# Case 1: Node has no child (leaf node)
if current_node.left is None and current_node.right is None:
return None
# Case 2: Node has only one child
if current_node.left is None:
return current_node.right
elif current_node.right is None:
return current_node.left
# Case 3: Node has two children
# Find inorder successor (smallest value in the right subtree)
successor = self._min_value_node(current_node.right)
current_node.key = successor.key # Replace current key with successor
# Delete the inorder successor from the right subtree
current_node.right = self._delete_recursive(current_node.right, successor.key)
return current_node
def _min_value_node(self, node):
"""Helper method to find the node with the smallest key in a subtree."""
current = node
while current.left is not None:
current = current.left
return current
# -------------------------
# EXAMPLE USAGE
# -------------------------
if __name__ == "__main__":
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)
print("Inorder Traversal (sorted):", bst.inorder_traversal())
print("Search for 40:", bst.search(40))
print("Search for 90:", bst.search(90))
print("Deleting 20...")
bst.delete(20)
print("Inorder Traversal after deletion:", bst.inorder_traversal())
print("Deleting 30...")
bst.delete(30)
print("Inorder Traversal after deletion:", bst.inorder_traversal())
print("Deleting 50...")
bst.delete(50)
print("Inorder Traversal after deletion:", bst.inorder_traversal())