BST - potatoscript/dsa GitHub Wiki
🧩 What is a Binary Search Tree (BST)?
A Binary Search Tree (BST) is a special type of binary tree in which the nodes are arranged in a specific order:
- Left child of a node has a value less than the node’s value.
- Right child of a node has a value greater than the node’s value.
This arrangement allows for quick searching, insertion, and deletion. Think of it like a well-organized library where each book is placed in order so you can quickly find what you need.
📚 Structure of a Binary Search Tree (BST)
- Each node in the BST contains a value.
- The left child has a value smaller than the parent node.
- The right child has a value greater than the parent node.
🔍 Simple Visual Example of a BST:
10
/ \
5 15
/ \ \
2 7 20
- Root = 10
- Left Child of 10 = 5
- Right Child of 10 = 15
- Children of 5 = 2 (left), 7 (right)
- Children of 15 = 20 (right)
Notice how for each node:
- The left child is smaller than the node.
- The right child is larger than the node.
🧩 How Does a Binary Search Tree Work?
The great thing about a BST is how it helps us quickly find values (just like searching for a book in an alphabetized library). Let’s explore how searching, inserting, and deleting works.
🧩 Searching for a Node in a BST
In a binary search tree, searching for a value follows these steps:
- Start at the root.
- If the value you are searching for is smaller than the current node’s value, move to the left child.
- If the value is greater, move to the right child.
- Repeat the process until you find the value or reach a null node.
Example: Searching for 7 in the BST
10
/ \
5 15
/ \ \
2 7 20
- Start at the root: 10.
- 7 is less than 10, so go left to node 5.
- 7 is greater than 5, so go right to node 7.
- Found 7! 🎉
🧩 Inserting a Node in a BST
Inserting a value into a BST is done by following these steps:
- Start at the root.
- If the value is smaller than the current node’s value, move to the left child.
- If the value is larger, move to the right child.
- Once you reach an empty spot (null), insert the new node there.
Example: Inserting 6 into the BST
10
/ \
5 15
/ \ \
2 7 20
- Start at the root: 10.
- 6 is less than 10, so go left to node 5.
- 6 is greater than 5, so go right to node 7.
- 6 is less than 7, so place the new node with value 6 to the left of 7.
New tree:
10
/ \
5 15
/ \ \
2 7 20
/
6
🧩 Deleting a Node in a BST
Deleting a node can be tricky because there are three possible cases to handle:
- Node has no children: Simply remove the node.
- Node has one child: Remove the node and connect its child to its parent.
- Node has two children: Replace the node with the in-order successor (the smallest node in the right subtree) or the in-order predecessor (the largest node in the left subtree), then delete the successor or predecessor.
Example: Deleting 15 from the BST
10
/ \
5 15
/ \ \
2 7 20
- 15 has one child (20).
- We simply remove 15 and connect 20 directly to 10.
New tree:
10
/ \
5 20
/ \
2 7
🧩 C# Code Example for Binary Search Tree
Let's write some C# code to create a simple Binary Search Tree that supports insertion, searching, and deletion.
📚 BST Node Class
public class BSTNode
{
public int Value;
public BSTNode Left;
public BSTNode Right;
public BSTNode(int value)
{
Value = value;
Left = null;
Right = null;
}
}
📚 BST Class
public class BinarySearchTree
{
public BSTNode Root;
// Constructor
public BinarySearchTree()
{
Root = null;
}
// Insertion Method
public void Insert(int value)
{
Root = InsertRec(Root, value);
}
private BSTNode InsertRec(BSTNode root, int value)
{
// If the tree is empty, return a new node
if (root == null)
{
root = new BSTNode(value);
return root;
}
// Otherwise, recur down the tree
if (value < root.Value)
root.Left = InsertRec(root.Left, value);
else if (value > root.Value)
root.Right = InsertRec(root.Right, value);
return root;
}
// Search Method
public bool Search(int value)
{
return SearchRec(Root, value);
}
private bool SearchRec(BSTNode root, int value)
{
// Base case: root is null or value is present at the root
if (root == null)
return false;
// Return true if value is found
if (root.Value == value)
return true;
// Otherwise, check the left or right subtree
if (value < root.Value)
return SearchRec(root.Left, value);
else
return SearchRec(root.Right, value);
}
// Delete Method (simplified for example)
public BSTNode Delete(BSTNode root, int value)
{
// If the tree is empty, return the root
if (root == null)
return root;
// Recur down the tree
if (value < root.Value)
root.Left = Delete(root.Left, value);
else if (value > root.Value)
root.Right = Delete(root.Right, value);
else
{
// Node with only one child or no child
if (root.Left == null)
return root.Right;
else if (root.Right == null)
return root.Left;
// Node with two children: get the inorder successor
root.Value = MinValue(root.Right);
// Delete the inorder successor
root.Right = Delete(root.Right, root.Value);
}
return root;
}
private int MinValue(BSTNode root)
{
int minValue = root.Value;
while (root.Left != null)
{
minValue = root.Left.Value;
root = root.Left;
}
return minValue;
}
}
🧩 Time Complexity (Big O) of BST Operations
- Insertion: O(log n) on average, but O(n) in the worst case (if the tree becomes unbalanced).
- Searching: O(log n) on average, but O(n) in the worst case (if the tree becomes unbalanced).
- Deletion: O(log n) on average, but O(n) in the worst case.
🧩 Practical Applications of Binary Search Trees (BST)
1. Database Indexing
BSTs can be used to index data in databases, allowing fast lookups, insertions, and deletions.
2. Sorting Algorithms
BSTs are the basis for algorithms like tree sort, where data can be inserted into the tree and then retrieved in sorted order.
3. Autocompletion
BSTs can be used for autocompletion systems where you search for the most relevant suggestions based on user input.