Insertion of a Binary Search Tree
Recursive Approach:
The recursive approach works by breaking the problem
into smaller subproblems:
If the tree is empty, create a new node and return
it.
Otherwise, compare the value to be inserted with the
current node:
o If it is smaller, insert it into the left
subtree.
o If it is larger, insert it into the right
subtree.
The function keeps calling itself until it finds the
correct position in the tree.
if (root == nullptr) {
return new Node(key);
}
if (key < root->data) {
root->left = insertRecursive(root->left, key);
} else if (key > root->data) {
root->right = insertRecursive(root->right, key);
}
return root;
}
Iterative Approach
The iterative approach works by using a loop instead
of recursion to find the correct position for the new
node:
If the tree is empty, create a new node and set it as
the root.
Otherwise, start from the root and traverse the tree
using a pointer.
Compare the value to be inserted with the current
node’s value:
o If it is smaller, move to the left subtree.
o If it is larger, move to the right subtree.
Keep track of the parent node while traversing.
Node* insertBST (Node* root, int key) {
Node* newNode = new Node(key);
if (root == nullptr) {
return newNode;
Node* curr = root;
Node* parent = nullptr;
while (curr != nullptr) {
parent = curr;
if (key < curr->key)
curr = curr->left;
else
curr = curr->right;
if (key < parent->key)
parent->left = newNode;
else
parent->right = newNode;
return root;
DELETION OF BST
Deleting a node from a BST involves three cases:
1. Node has no children (Leaf Node)
→ Simply delete the node.
2. Node has one child
→ Replace the node with its child and delete it.
3. Node has two children
→ Find the inorder successor (smallest value in the
right subtree) or inorder predecessor (largest value
in the left subtree).
→ Replace the node’s value with the
successor/predecessor.
→ Delete the successor/predecessor node.
Iterative Approach of Deletion in BST
Node* deleteNode (Node* root, int key) {
if (root == nullptr) return root;
Node* curr = root;
Node* parent = nullptr;
// Step 1: Find the node to be deleted
while (curr! = nullptr && curr->key != key) {
parent = curr;
if (key < curr->key)
curr = curr->left;
else
curr = curr->right;
}
if (curr == nullptr)
return root;
// Case 1: Node has no children (Leaf node)
if (curr->left == nullptr && curr->right == nullptr) {
if (curr == root)
return nullptr;
if (parent->left == curr)
parent->left = nullptr;
else
parent->right = nullptr;
delete curr;
// Case 2: Node has one child
else if (curr->left == nullptr || curr->right ==
nullptr) {
Node* child = (curr->left) ? curr->left : curr-
>right;
if (curr == root)
return child;
if (parent->left == curr)
parent->left = child;
else
parent->right = child;
delete curr;
}
// Case 3: Node has two children
else {
Node* successor = findMin(curr->right);
int val = successor->key;
root = deleteNode(root, successor->key); // Delete
successor
curr->key = val;
return root;
Recursive Approach:
Node* deleteLeafNode (Node* root, int key) {
if (root == nullptr)
return nullptr;
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 == nullptr && root->right ==
nullptr) {
delete root;
return nullptr;
return root;
Minimum and Maximum of BST
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int val) {
data = val;
left = right = nullptr;
}
};
// Function to find the minimum value in BST
int findMin(Node* root) {
if (root == nullptr) {
return -1;
}
while (root->left != nullptr) {
root = root->left;
}
return root->data;
}
// Function to find the maximum value in BST
int findMax(Node* root) {
if (root == nullptr) {
return -1;
}
while (root->right != nullptr) {
root = root->right;
}
return root->data;
}
int main ()
{
Node* root = new Node (5);
root->left = new Node (3);
root->right = new Node (8);
root->left->left = new Node (1);
root->left->right = new Node (4);
root->right->left = new Node (7);
root->right->right = new Node (10);
cout << "Minimum Value: " << findMin(root) << "\n";
cout << "Maximum Value: " << findMax(root) << "\n”;
return 0;
Output:
Minimum Value: 1
Maximum Value: 10
Finding K-th smallest element in BST:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = right = NULL;
}
};
Node* insert (Node* root, int value) {
if (root == NULL) {
return new Node(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}
void inorderTraversal (Node* root, int& count, int k, int&
result) {
if (root == NULL || count >= k) {
return;
}
inorderTraversal(root->left, count, k, result);
count++;
if (count == k) {
result = root->data;
return;
}
inorderTraversal(root->right, count, k, result);
}
int kthsmall (Node* root, int k) {
int count = 0;
int result = -1;
inorderTraversal (root, count, k, result);
return result;
}
int main () {
int num;
cout << "Enter the number of elements in the BST: ";
cin >> num;
Node* root = NULL;
cout << "Enter the elements:\n";
for (int i = 0; i < num; i++) {
int value;
cin >> value;
root = insert (root, value);
}
int k;
cout << "Enter the value of k: ";
cin >> k;
if (k <= 0 || k > num) {
cout << "Invalid value of k! \n";
} else {
int result = kthsmall (root, k);
cout << k << "th smallest element is " << result
<< "\n";
}
return 0;
}
Output:
Enter the number of elements in the BST: 5
Enter the elements:
45
67
89
55
Enter the value of k: 2
2th smallest element is 55
