Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Binary Search Tree (BST) is a binary tree that maintains the invariant: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger
A Binary Search Tree (BST) is a binary tree that maintains the invariant: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.
This ordering enables O(log n) search, insertion, and deletion on average.
How It Works
Starting at the root, compare the target with the current node.
If equal, found.
If less, go left.
If greater, go right.
Repeat until found or null.
Insertion follows the same path and adds a leaf.
Deletion has three cases: leaf (remove directly), one child (bypass), and two children (replace with inorder successor).
The tree's height determines performance — balanced BSTs achieve O(log n), while degenerate trees (e.g., inserting sorted data) degrade to O(n).
Self-balancing variants (AVL, Red-Black) maintain O(log n) guarantees.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Search (average) | O(log n) | O(1) |
| Search (worst) | O(n) | O(1) |
| Insert (average) | O(log n) | O(1) |
| Insert (worst) | O(n) | O(1) |
| Delete (average) | O(log n) | O(1) |
| Delete (worst) | O(n) | O(1) |
| Find Min / Max | O(h) | O(1) |
Best Use Cases
- Implementing ordered sets and maps (SortedSet, TreeMap)
- In-memory sorting and range queries
- Database indexes (B-tree variant is more common)
- Expression evaluation and symbol tables
- Priority queue with deletion flexibility
Worked Example
Search, min/max, insert 55, and delete 50 in a balanced BST
Input: root 50, left 30, right 70; 30 → (20, 40); 70 → (60, 80)- 1 Search for 55: start at 50, go right (55 > 50) to 70, then left (55 < 70) to 60, then left to the empty slot — 55 is not present.
- 2 FindMin walks only left: 50 → 30 → 20. FindMax walks only right: 50 → 70 → 80.
- 3 Insert 55: following the search path, it attaches as the left child of 60.
- 4 Delete 50 (root with two children): find its inorder successor (60), copy it up, then delete the successor from the right subtree.
- 5 The tree stays a valid BST throughout: left < node < right at every node.
Pseudocode
function search(root, target):
current = root
while current is not null:
if target == current.value:
return current
else if target < current.value:
current = current.left
else:
current = current.right
return null function insert(root, value):
if root is null:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else if value > root.value:
root.right = insert(root.right, value)
return root function findMin(root):
if root is null: return null
current = root
while current.left is not null:
current = current.left
return current function findMax(root):
if root is null: return null
current = root
while current.right is not null:
current = current.right
return current function delete(root, target):
if root is null:
return null
if target < root.value:
root.left = delete(root.left, target)
else if target > root.value:
root.right = delete(root.right, target)
else:
if root.left is null: return root.right // 0 or 1 child
if root.right is null: return root.left
// Two children: replace with inorder successor
succ = findMin(root.right)
root.value = succ.value
root.right = delete(root.right, succ.value)
return root Insert
Select an operation to begin.