ayodhyya.comA Binary Search Tree (BST) is a binary tree that satisfies the BST property: for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger than the node's key. This property enables efficient search, insertion, and deletion operations, averaging O(log n) time for balanced trees.
BSTs are fundamental to computer science, forming the basis for more advanced structures like AVL trees, Red-Black trees, and Treaps. The inorder traversal of a BST yields keys in sorted ascending order, making it useful for range queries and sorted data retrieval.
Search and Insert Operations
Search recursively compares the target with the current node β go left if smaller, right if larger β until found or a null child is reached. Insertion follows the same path and attaches the new node at the first empty position that preserves the BST property.
Node* search(Node* root, int key) {
if (!root || root->key == key) return root;
if (key < root->key) return search(root->left, key);
return search(root->right, key);
}
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->key)
root->left = insert(root->left, key);
else root->right = insert(root->right, key);
return root;
}Deletion in BST
Deletion has three cases: leaf (simply remove), one child (replace with child), and two children (replace with inorder successor β the smallest in the right subtree). The successor always has at most one child, simplifying the recursive removal.
Node* deleteNode(Node* root, int key) {
if (!root) return root;
if (key < root->key) root->left = deleteNode(root->left, key);
else if (key > root->key) root->right = deleteNode(root->right, key);
else {
if (!root->left) { Node* tmp = root->right; delete root; return tmp; }
if (!root->right) { Node* tmp = root->left; delete root; return tmp; }
Node* succ = root->right;
while (succ->left) succ = succ->left;
root->key = succ->key;
root->right = deleteNode(root->right, succ->key);
}
return root;
}Frequently Asked Questions
What is the worst-case time complexity of BST operations?
In the worst case (skewed tree), search, insert, and delete degrade to O(n). This occurs when keys are inserted in sorted or reverse-sorted order without rebalancing.
What is the inorder successor?
The inorder successor of a node is the smallest node in its right subtree. It is found by moving one step right, then repeatedly left until a null left child is reached.
Originally published on Ayodhyya. Last updated June 1, 2026.