DSA Binary Search Trees

DSA Binary Search Trees (BST) – Complete Beginner Guide

(Concept • Properties • Operations • Examples • Code • Complexity)

A Binary Search Tree (BST) is a special type of Binary Tree that keeps elements ordered, enabling fast search, insertion, and deletion.

1️⃣ What is a Binary Search Tree?

A BST follows this ordering property for every node:

Left Subtree < Root < Right Subtree

This rule applies recursively to all subtrees.

Example

2️⃣ Why Use a BST?

✔ Faster searching than arrays & linked lists
✔ Keeps data sorted
✔ Efficient insert & delete
✔ Foundation for advanced trees (AVL, Red-Black)

3️⃣ Key Properties of BST

Left child values are smaller than node
Right child values are greater than node
No duplicate keys (standard BST)
Inorder traversal gives sorted order

4️⃣ BST Traversals (Important)

For a BST:

Inorder → Sorted output
Preorder → Copy tree
Postorder → Delete tree

Example Inorder

5️⃣ BST Node Structure (C++)

6️⃣ Insert Operation in BST

Logic

If tree is empty → new node becomes root
If value < root → go left
If value > root → go right

Code (C++)

7️⃣ Search Operation in BST

Logic

Compare key with root
Move left or right accordingly

Code

8️⃣ Delete Operation in BST

( Very Important for Interviews)

Three Cases

Leaf Node → delete directly
One Child → replace with child
Two Children → replace with Inorder Successor

Helper (Find Minimum)

Delete Code

Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

Node* deleteNode(Node* root, int key) {

if (root == NULL) return root;if (key < root->data)

root->left = deleteNode(root->left, key);

else if (key > root->data)

root->right = deleteNode(root->right, key);

else {

if (root->left == NULL) {

Node* temp = root->right;

delete root;

return temp;

}

else if (root->right == NULL) {

Node* temp = root->left;

delete root;

return temp;

}

Node* temp = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

}

return root;

}

9️⃣ Time Complexity

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Worst case happens when BST becomes skewed.

🔟 Space Complexity

O(h) where h is tree height
Recursive calls use stack space

1️⃣1️⃣ BST vs Binary Tree

Feature	Binary Tree	BST
Order	❌ No	✅ Yes
Search	O(n)	O(log n) avg
Sorted Output	❌ No	✅ Yes

1️⃣2️⃣ Common BST Problems (Interview Favorites)

✔ Validate BST
✔ Lowest Common Ancestor (LCA)
✔ Kth smallest element
✔ Range sum in BST
✔ Convert BST to sorted array

Interview Questions (BST)

Q1. Why inorder traversal gives sorted order in BST?
👉 Due to left < root < right property

Q2. What is inorder successor?
👉 Smallest node in right subtree

Q3. When does BST become inefficient?
👉 When it becomes skewed

Final Summary

✔ BST maintains sorted structure
✔ Left < Root < Right
✔ Inorder traversal gives sorted order
✔ Average O(log n) operations
✔ Extremely important for DSA interviews

DSA Binary Search Trees