Introduction
Binary Search Trees (BSTs) are a fundamental data structure in computer science that combine the hierarchical structure of binary trees with the power of ordering to enable efficient searching, insertion, and deletion. If you're preparing for coding interviews or aiming to strengthen your data structures knowledge, mastering BSTs is essential.
In this blog, we will explore BST concepts in depth, discuss key properties, implement core operations in Java, analyze time complexity, and provide practice problems to level up your skills.
What is a Binary Search Tree?
A Binary Search Tree is a binary tree with the following property:
For every node, all nodes in the left subtree have values less than the node's value, and all nodes in the right subtree have values greater than the node's value.
This ordering property helps maintain a sorted structure, enabling efficient search and update operations.
Example BST
15
/ \
10 20
/ \ \
8 12 25
All nodes in left subtree of 15 (8, 10, 12) are less than 15.
All nodes in right subtree of 15 (20, 25) are greater than 15.
Key Properties of BST
Ordering: Left subtree < Node < Right subtree for every node.
No duplicates: Typically, BSTs do not allow duplicates. If needed, duplicates can be stored either consistently in the left or right subtree.
Height and Balance: The height affects efficiency. Balanced BSTs maintain height ≈ O(log n). Unbalanced BSTs degrade to O(n) height.
Recursive Structure: Each subtree is itself a BST.
Java Implementation of BST Node
public class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
left = right = null;
}
}
Basic Operations on BST in Java
1. Search in BST
Search is efficient due to the ordering property — at each node, decide to go left or right.
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val)
return root;
if (val < root.val)
return searchBST(root.left, val);
else
return searchBST(root.right, val);
}
2. Insertion in BST
Insert a new value by maintaining the BST property. Recursively find the correct position.
public TreeNode insertBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertBST(root.left, val);
} else if (val > root.val) {
root.right = insertBST(root.right, val);
}
// If val == root.val, duplicates not allowed; ignore or handle separately
return root;
}
3. Deletion in BST
Deleting a node is trickier and involves 3 cases:
Leaf node: Remove node directly.
One child: Replace node with child.
Two children: Replace node’s value with the inorder successor (smallest in right subtree), then delete the successor node.
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// Node to be deleted found
if (root.left == null) return root.right;
else if (root.right == null) return root.left;
// Node with two children: Get inorder successor (smallest in right subtree)
root.val = minValue(root.right);
// Delete the inorder successor
root.right = deleteNode(root.right, root.val);
}
return root;
}
private int minValue(TreeNode node) {
int minv = node.val;
while (node.left != null) {
minv = node.left.val;
node = node.left;
}
return minv;
}
4. Inorder Traversal (Sorted order output)
Inorder traversal visits nodes in sorted order (left, root, right):
public void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
}
Time Complexity Analysis of BST Operations
1. Search
Average Case: O(log n)
Worst Case: O(n)
2. Insert
Average Case: O(log n)
Worst Case: O(n)
3. Delete
Average Case: O(log n)
Worst Case: O(n)
In a balanced BST (like AVL or Red-Black Trees), most operations remain O(log n), whereas an unbalanced BST can degrade to O(n).
Real-world Analogy
Think about searching for a contact in a sorted phonebook rather than a random list. Because the entries are sorted, you can quickly narrow down the search by dividing the book in half repeatedly — just like BST’s divide-and-conquer approach.
Practice Problems
Validate Binary Search Tree – Medium – LeetCode#98
Insert into a Binary Search Tree – Medium – LeetCode#701
Delete Node in a BST – Medium – LeetCode#450
Lowest Common Ancestor of a BST – Easy – LeetCode#235
Closest Binary Search Tree Value – Medium – LeetCode#270
Tips for Interview Prep
Understand the BST ordering property deeply.
Implement recursive and iterative solutions for search, insert, and delete.
Handle edge cases: empty tree, duplicates, single child nodes.
Know how to find the inorder successor and predecessor.
Practice tree traversals (inorder, preorder, postorder).
Remember balancing affects performance; understand basics of AVL/Red-Black trees (optional).
Wrapping Up
BSTs are crucial data structures enabling fast lookup, insertion, and deletion. Their sorted nature allows algorithms to run in logarithmic time on balanced trees, making them extremely useful in many applications.
Mastering BST operations and understanding their time complexities will give you a significant edge in interviews and coding challenges.
Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram
