Table of contents
- Q1. Implement a binary search tree with insertion, deletion, and search operations.
- Q2. Solve the "validate if a tree is a binary search tree" problem.
- Q3. Solve the "find the kth smallest/largest element in a BST" problem.
- Q4. Solve the "find the floor and ceil of a given key in a BST" problem.
- Q5. Solve the "convert a BST to a sorted doubly linked list" problem.
Today, I focused on mastering binary search trees (BSTs) by implementing essential operations and solving problems that leverage their properties. I began by implementing a BST with insertion, deletion, and search operations, ensuring efficient element management. Then, I tackled the "validate if a tree is a binary search tree" problem, verifying whether the tree satisfies BST conditions. I also solved the "kth smallest/largest element in a BST" problem, followed by finding the floor and ceil of a given key in a BST. Finally, I converted a BST into a sorted doubly linked list, exploring tree-to-list transformations.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement a binary search tree with insertion, deletion, and search operations.
#include <iostream>
using namespace std;
struct Node{
int data; // Data of the node
Node* left; // Pointer to left child
Node* right; // Pointer to right child
// Constructor to initialize a node with a given value
Node(int val){
data = val; // Set the node's data to the given value
left = NULL; // Initialize left child to NULL
right = NULL; // Initialize right child to NULL
}
};
// Insertion function to insert a node with a given key into the BST
Node* insertion(Node* root, int key){
if(root == NULL){ // If the tree is empty, create a new node
return new Node(key);
}
// Recursively traverse to the left or right subtree based on the value of key
if(root->data > key){
root->left = insertion(root->left, key); // Insert into the left subtree
}
else if(root->data < key){
root->right = insertion(root->right, key); // Insert into the right subtree
}
return root; // Return the root of the tree
}
// Search function to find a node with the given key in the BST
Node* search_BST(Node* root, int key){
if(root == NULL){ // If the node is NULL, return NULL (not found)
return NULL;
}
if(root->data == key){ // If the key is found, return the node
return root;
}
else if(key < root->data){ // If key is smaller, search the left subtree
return search_BST(root->left, key);
}
else if(key > root->data){ // If key is larger, search the right subtree
return search_BST(root->right, key);
}
}
// Function to find the inorder successor of a node (smallest node in right subtree)
Node* find_inorder_successor(Node* root){
Node* curr = root;
while(curr != NULL && curr->left != NULL){ // Traverse leftmost node of the right subtree
curr = curr->left;
}
return curr; // Return the inorder successor
}
// Deletion function to delete a node with the given key in the BST
Node* deletion(Node* root, int key){
if(key < root->data){ // If the key is smaller, delete from the left subtree
root->left = deletion(root->left, key);
}
else if(key > root->data){ // If the key is larger, delete from the right subtree
root->right = deletion(root->right, key);
}
else{ // If the key is found
// Case 1: Node has no children (leaf node)
if(root->left == NULL){
Node* temp = root->right; // Get the right child
free(root); // Free the current node
return temp; // Return the right child
}
// Case 2: Node has only one child (left or right)
else if(root->right == NULL){
Node* temp = root->left; // Get the left child
free(root); // Free the current node
return temp; // Return the left child
}
// Case 3: Node has two children
Node* temp = find_inorder_successor(root->right); // Find the inorder successor
root->data = temp->data; // Copy the inorder successor's data to the current node
root->right = deletion(root->right, temp->data); // Delete the inorder successor
}
return root; // Return the modified root
}
// Inorder traversal function to print the nodes of the BST in sorted order
void inorder_traversal(Node* root){
if(root == NULL){
return; // Base case: if the node is NULL, return
}
inorder_traversal(root->left); // Visit left subtree
cout << root->data << " "; // Print the current node's data
inorder_traversal(root->right); // Visit right subtree
}
int main(){
int n;
cout << "How many elements does the BST have?: ";
cin >> n; // Get the number of elements to insert into the BST
int arr[n];
cout << "Enter all of its elements: ";
for(int i = 0; i < n; i++){
cin >> arr[i]; // Read the elements into the array
}
Node* root = new Node(arr[0]); // Create the root node of the BST
for(int i = 1; i < n; i++){
insertion(root, arr[i]); // Insert the remaining elements into the BST
}
// Perform inorder traversal and print the elements of the BST
inorder_traversal(root);
int key;
cout << endl;
cout << "Enter the element to be searched: ";
cin >> key; // Get the key to search for
// Search the BST for the given key
if(search_BST(root, key) == NULL){
cout << "Key does not exist in BST";
}
else{
cout << "Key does exist in BST";
}
// Deleting a node from the BST
deletion(root, 4); // Deleting node with value 4
// Perform inorder traversal again to display the tree after deletion
cout << endl;
inorder_traversal(root);
return 0;
}
This code implements a binary search tree (BST) with essential operations: insertion, deletion, search, and inorder traversal. The Node structure represents a node in the BST, with data and pointers to the left and right children. The insertion function inserts a new node with a specified key, ensuring the BST property is maintained. The search_BST function searches for a node with a given key, returning the node if found, or NULL if not. The deletion function deletes a node by handling three cases: when the node has no children, one child, or two children (replacing it with the inorder successor in the case of two children). The inorder_traversal function prints the elements of the BST in sorted order. In the main function, a BST is constructed from user input, and operations like search and deletion are performed. After deletion, the tree is printed again using inorder traversal to show the updated structure.
Q2. Solve the "validate if a tree is a binary search tree" problem.
#include <iostream>
using namespace std;
struct Node {
int data; // Data of the node
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
// Constructor to initialize a node with the given value
Node(int val) {
data = val;
left = NULL;
right = NULL;
}
};
// Function to validate if the binary tree is a BST
bool validateBST(Node* root, Node* min_value = NULL, Node* max_value = NULL) {
// Base case: If the node is NULL, it is considered valid
if (root == NULL) {
return true;
}
// If the node's value is less than or equal to the minimum allowed value, the tree is invalid
if (min_value != NULL && root->data <= min_value->data) {
return false;
}
// If the node's value is greater than or equal to the maximum allowed value, the tree is invalid
if (max_value != NULL && root->data >= max_value->data) {
return false;
}
// Recursively validate the left subtree with updated maximum value as the root's data
bool leftValidity = validateBST(root->left, min_value, root);
// Recursively validate the right subtree with updated minimum value as the root's data
bool rightValidity = validateBST(root->right, root, max_value);
// The tree is valid if both the left and right subtrees are valid
return leftValidity && rightValidity;
}
// Function to insert a new node with a given key into the BST
Node* insertion(Node* root, int key) {
if (root == NULL) { // If the tree is empty, create a new node
return new Node(key);
}
// Recursively traverse to the left or right subtree based on the value of the key
if (root->data > key) {
root->left = insertion(root->left, key); // Insert into the left subtree
}
else if (root->data < key) {
root->right = insertion(root->right, key); // Insert into the right subtree
}
return root; // Return the root of the tree
}
int main() {
// Example 1: Valid BST
Node* root1 = new Node(2);
root1->left = new Node(1);
root1->right = new Node(3);
// Validate if the tree is a BST
if (!validateBST(root1, NULL, NULL)) {
cout << "BST is invalid";
}
else {
cout << "BST is valid";
}
cout << endl;
// Example 2: Invalid BST
Node* root2 = new Node(4);
root2->left = new Node(5); // Left child is greater than the root, so it's invalid
root2->right = new Node(6);
// Validate if the tree is a BST
if (!validateBST(root2, NULL, NULL)) {
cout << "BST is invalid";
}
else {
cout << "BST is valid";
}
return 0;
}
This code defines a binary search tree (BST) and validates if a given binary tree satisfies the BST property. The Node structure represents a node in the tree, holding data and pointers to its left and right children. The validateBST function checks if the binary tree is a valid BST by ensuring that for every node, its value is greater than the maximum value of the left subtree and less than the minimum value of the right subtree. It uses recursive calls to validate both the left and right subtrees with updated minimum and maximum bounds. The insertion function is used to insert nodes into the BST, maintaining the correct structure. In the main function, two example trees are created: one valid BST and one invalid BST. The validity of both trees is checked using the validateBST function, and the result is printed to the console. The first tree is valid, and the second is invalid because the left child of the root is greater than the root itself.
Q3. Solve the "find the kth smallest/largest element in a BST" problem.
#include <iostream>
using namespace std;
#include <vector>
struct Node{
int data; // Data of the node
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
// Constructor to initialize a node with the given value
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
// Function to insert a node with a given key into the BST
Node* insertion(Node* root, int key){
if(root == NULL){ // If the tree is empty, create a new node
return new Node(key);
}
// Recursively traverse to the left or right subtree based on the value of key
if(root->data > key){
root->left = insertion(root->left, key); // Insert into the left subtree
}
else if(root->data < key){
root->right = insertion(root->right, key); // Insert into the right subtree
}
return root; // Return the root of the tree
}
// Function to perform an inorder traversal of the BST and store elements in a vector
void inorder_traversal_and_insertion(Node* root, vector<int>& v){
if(root == NULL){
return;
}
inorder_traversal_and_insertion(root->left, v); // Traverse left subtree
v.push_back(root->data); // Add current node to the vector
inorder_traversal_and_insertion(root->right, v); // Traverse right subtree
}
// Function to find the kth smallest or largest element from the sorted array
void find_kth_smallest_largest(vector<int>& v, int k, int c){
if (c == 1){
// If c is 1, find the kth smallest element (0-based index)
cout << v[k - 1];
}
else if (c == 2){
// If c is 2, find the kth largest element (0-based index)
cout << v[v.size() - k];
}
}
int main(){
int n, c, k;
cout << "How many elements does the BST have?: ";
cin >> n; // Get the number of elements to insert into the BST
int arr[n];
cout << "Enter all of its elements: ";
for(int i = 0; i < n; i++){
cin >> arr[i]; // Read the elements into the array
}
// Create the root node of the BST with the first element
Node* root = new Node(arr[0]);
// Insert the remaining elements into the BST
for(int i = 1; i < n; i++){
insertion(root, arr[i]);
}
cout << "Do you want the kth largest or smallest?(1-smallest, 2-largest): ";
cin >> c; // Get the choice for kth smallest or largest (1 for smallest, 2 for largest)
cout << "Find the value of k: ";
cin >> k; // Get the value of k (the position of the element)
vector<int> v;
inorder_traversal_and_insertion(root, v); // Perform inorder traversal to get sorted elements
find_kth_smallest_largest(v, k, c); // Find and print the kth smallest or largest element
return 0;
}
This code implements a binary search tree (BST) and provides functionality to find the kth smallest or kth largest element in the tree. First, it defines a Node structure that represents each node in the tree with its data and pointers to left and right children. The insertion function is used to insert nodes into the BST, maintaining the correct structure. The inorder_traversal_and_insertion function performs an inorder traversal of the tree, storing the node values in a vector, ensuring the elements are sorted. The user is then prompted to input the number of elements for the BST, the elements themselves, and whether they want to find the kth smallest or kth largest element. Based on the user's choice (1 for smallest, 2 for largest), the find_kth_smallest_largest function is called to print the appropriate element from the sorted vector. The program efficiently converts the tree into a sorted list using inorder traversal, allowing quick access to the desired element based on its position.
Q4. Solve the "find the floor and ceil of a given key in a BST" problem.
#include <iostream>
using namespace std;
#include <vector>
struct Node{
int data; // Data of the node
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
// Constructor to initialize a node with the given value
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
// Function to insert a node with a given key into the BST
Node* insertion(Node* root, int key){
if(root == NULL){ // If the tree is empty, create a new node
return new Node(key);
}
// Recursively traverse to the left or right subtree based on the value of key
if(root->data > key){
root->left = insertion(root->left, key); // Insert into the left subtree
}
else if(root->data < key){
root->right = insertion(root->right, key); // Insert into the right subtree
}
return root; // Return the root of the tree
}
// Function to perform an inorder traversal of the BST and store elements in a vector
void inorder_traversal_and_insertion(Node* root, vector<int>& v){
if(root == NULL){
return;
}
inorder_traversal_and_insertion(root->left, v); // Traverse left subtree
v.push_back(root->data); // Add current node to the vector
inorder_traversal_and_insertion(root->right, v); // Traverse right subtree
}
// Function to find the floor and ceiling of a given key in a sorted array
void floor_and_ceil(vector<int>& v, int key) {
int floor_val = -1; // Initialize floor as -1 (no valid floor)
int ceil_val = -1; // Initialize ceiling as -1 (no valid ceiling)
// Traverse the sorted array to find the floor and ceiling
for (int i = 0; i < v.size(); i++) {
if (v[i] == key) {
// If key matches an element, floor and ceil are the same
floor_val = key;
ceil_val = key;
break;
}
if (v[i] < key) {
// Update floor to the current value
floor_val = v[i];
}
if (v[i] > key && ceil_val == -1) {
// Update ceiling to the first element greater than the key
ceil_val = v[i];
}
}
// Print results
if (floor_val == -1) {
cout << "No floor exists for the key." << endl;
} else {
cout << "The floor of the key is: " << floor_val << endl;
}
if (ceil_val == -1) {
cout << "No ceiling exists for the key." << endl;
} else {
cout << "The ceiling of the key is: " << ceil_val << endl;
}
}
int main(){
int n, k;
cout << "How many elements does the BST have?: ";
cin >> n; // Get the number of elements to insert into the BST
int arr[n];
cout << "Enter all of its elements: ";
for(int i = 0; i < n; i++){
cin >> arr[i]; // Read the elements into the array
}
// Create the root node of the BST with the first element
Node* root = new Node(arr[0]);
// Insert the remaining elements into the BST
for(int i = 1; i < n; i++){
insertion(root, arr[i]);
}
cout << "For what value do you want the ceil and floor?: ";
cin >> k; // Get the key for which we need to find floor and ceil
vector<int> v;
inorder_traversal_and_insertion(root, v); // Perform inorder traversal to get sorted elements
floor_and_ceil(v, k); // Find and print the floor and ceil of the key
return 0;
}
This code implements a binary search tree (BST) and provides functionality to find the floor and ceiling values for a given key. The Node structure represents a node in the tree with data and pointers to left and right children. The insertion function is used to insert nodes into the BST while maintaining the BST properties. The inorder_traversal_and_insertion function traverses the tree in an inorder manner and stores the node values in a vector, which results in a sorted array. The floor_and_ceil function then finds the floor and ceiling of a given key by iterating through the sorted vector: the floor is the largest value smaller than or equal to the key, and the ceiling is the smallest value greater than or equal to the key. The user is prompted to input the elements for the BST and a key to find the floor and ceiling values, which are then printed. This approach leverages inorder traversal to convert the BST into a sorted array and then searches for the desired values in that array.
Q5. Solve the "convert a BST to a sorted doubly linked list" problem.
#include <iostream>
using namespace std;
struct Node{
int data; // Data of the node
Node* left; // Pointer to the left child
Node* right; // Pointer to the right child
// Constructor to initialize a node with the given value
Node(int val){
data = val;
left = NULL;
right = NULL;
}
};
Node* prevptr = NULL; // Pointer to keep track of the previous node during the conversion
Node* headDLL = NULL; // Pointer to the head of the doubly linked list
// Insertion function to insert a node with a given key into the BST
Node* insertion(Node* root, int key){
if(root == NULL){ // If the tree is empty, create a new node
return new Node(key);
}
// Recursively traverse to the left or right subtree based on the value of key
if(root->data > key){
root->left = insertion(root->left, key); // Insert into the left subtree
}
else if(root->data < key){
root->right = insertion(root->right, key); // Insert into the right subtree
}
return root; // Return the root of the tree
}
// Function to convert the given BST to a sorted doubly linked list
void convert_to_DLL(Node* root){
if(root == NULL){ // Base case: if the node is NULL, return
return;
}
// Recursively convert the left subtree first
convert_to_DLL(root->left);
// If prevptr is NULL, it means we are at the leftmost node, so set headDLL to the current node
if(prevptr == NULL){
headDLL = root;
}
else{
// Set the previous node's right pointer to the current node
root->left = prevptr;
// Set the current node's left pointer to the previous node
prevptr->right = root;
}
// Update prevptr to the current node, as it's now the most recent node in the DLL
prevptr = root;
// Recursively convert the right subtree
convert_to_DLL(root->right);
}
// Function to print the doubly linked list
void print_DLL(Node* head) {
Node* temp = head;
cout << "Doubly Linked List: ";
while (temp != NULL) { // Traverse the DLL and print each node's data
cout << temp->data << " ";
temp = temp->right;
}
cout << endl;
}
int main(){
int n;
cout << "How many elements does the BST have?: ";
cin >> n; // Get the number of elements to insert into the BST
int arr[n];
cout << "Enter all of its elements: ";
for(int i = 0; i < n; i++){
cin >> arr[i]; // Read the elements into the array
}
// Create the root node of the BST with the first element
Node* root = new Node(arr[0]);
// Insert the remaining elements into the BST
for(int i = 1; i < n; i++){
insertion(root, arr[i]);
}
// Convert the BST to a sorted doubly linked list
convert_to_DLL(root);
// Print the resulting doubly linked list
print_DLL(headDLL);
return 0;
}
This C++ program converts a Binary Search Tree (BST) into a sorted Doubly Linked List (DLL). It first defines a Node structure for the BST, which contains data, a pointer to the left child, and a pointer to the right child. The insertion function is used to insert elements into the BST based on their values. After constructing the BST, the convert_to_DLL function recursively traverses the tree in an in-order fashion, adjusting the left and right pointers of the nodes to link them as a DLL. The prevptr pointer keeps track of the previous node during traversal, and the headDLL pointer points to the head of the DLL. The program ends by printing the resulting DLL using the print_DLL function, which traverses the DLL from the head to the last node and outputs the node data in order. The main function reads the input values, constructs the BST, converts it to a DLL, and displays the DLL.
Today's practice strengthened my understanding of binary search trees and their operations. From building a BST with core functions to solving problems like finding the kth smallest element and converting the tree to a doubly linked list, I gained deeper insights into tree manipulation and traversal techniques. These exercises have equipped me with a solid foundation in BST-related challenges, and I'm eager to continue advancing my skills in tree algorithms!