🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
A Binary Search Tree (BST) is a tree in which all the nodes follow the left child < parent < right child property. This property ensures that the left subtree contains elements less than the node, and the right subtree contains elements greater than the node. BSTs are widely used due to their efficiency in many operations, like search, insert, and delete.
2. Program Overview
In this program, we will:
1. Define a node structure for our BST.
2. Implement the following BST operations:
- Insertion: To add an element to the BST.
- Deletion: To remove an element from the BST.
- Search: To check if an element exists in the BST.
- Inorder Traversal: To display the BST in ascending order.
3. Code Program
#include <stdio.h>
#include <stdlib.h>
// Define the structure for our BST node
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Function to create a new node
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node into BST
Node* insert(Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Function to find the node with minimum value
Node* minValueNode(Node* root) {
Node* current = root;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
// Function to delete a node
Node* deleteNode(Node* root, int value) {
if (root == NULL) return root;
// Recursive calls for ancestors of the node to be deleted
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// Node with one child or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Node with two children
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Function to perform in-order traversal
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
printf("Inorder traversal: ");
inorder(root);
printf("\n");
printf("Delete 20: ");
root = deleteNode(root, 20);
inorder(root);
printf("\n");
printf("Delete 30: ");
root = deleteNode(root, 30);
inorder(root);
printf("\n");
printf("Delete 50: ");
root = deleteNode(root, 50);
inorder(root);
printf("\n");
return 0;
}
Output:
Inorder traversal: 20 30 40 50 60 70 80 Delete 20: 30 40 50 60 70 80 Delete 30: 40 50 60 70 80 Delete 50: 40 60 70 80
4. Step By Step Explanation
1. We begin by defining a node structure for our BST. Each node contains an integer data, a pointer to the left child, and a pointer to the right child.
2. The insert function adds a new node to the BST while maintaining its properties.
3. The minValueNode function returns the node with the smallest value greater than the passed node.
4. The deleteNode function removes a node from the BST and adjusts the tree to preserve the BST property.
5. The inorder function traverses the BST in ascending order.
6. In the main function, we demonstrate the insertion of several nodes, in-order traversal, and deletion of nodes followed by traversal to show the updated BST.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment