Welcome to Day 20 of my 100 Days of DSA challenge! Today, I tackled five problems focused on Binary Search Trees (BSTs). From understanding their fundamental operations to solving more advanced challenges, these problems deepened my understanding of this essential data structure.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let's dive into how I approached each one and the insights gained along the way! 🤖✨
1. Implement a Binary Search Tree
In this program, a Binary Search Tree (BST) is implemented using a class with several operations. The Node structure represents each node of the tree, containing data and pointers to left and right children. The binary_search_tree class includes methods for inserting, searching, and deleting nodes, along with an inorder traversal to display the tree in ascending order. The insert method ensures that nodes are added according to the BST property, and the search method checks if a value exists in the tree. The delete method handles three cases: deleting a node with no children, one child, or two children by replacing the node with its inorder successor.
Code:
#include <iostream>
using namespace std;
// Define the structure for the node of the BST
struct Node {
int data;
Node* left;
Node* right;
// Constructor for initializing a node
Node(int value) {
data = value;
left = right = nullptr;
}
};
// Class to represent the Binary Search Tree
class binary_search_tree {
private:
Node* root;
// Helper function for insert operation
Node* insert(Node* node, int data) {
if (node == nullptr) {
return new Node(data); // If the node is empty, create a new node
}
if (data < node->data) {
node->left = insert(node->left, data); // Insert in the left subtree
} else if (data > node->data) {
node->right = insert(node->right, data); // Insert in the right subtree
}
return node;
}
// Helper function for search operation
bool search(Node* node, int key) {
if (node == nullptr) {
return false; // If node is null, the element is not found
}
if (node->data == key) {
return true; // Element found
}
if (key < node->data) {
return search(node->left, key); // Search in the left subtree
} else {
return search(node->right, key); // Search in the right subtree
}
}
// Helper function to find the minimum value node in the BST
Node* find_min(Node* node) {
while (node && node->left != nullptr) {
node = node->left;
}
return node;
}
// Helper function for deletion operation
Node* delete_node(Node* node, int key) {
if (node == nullptr) {
return node; // If the node is null, return null
}
if (key < node->data) {
node->left = delete_node(node->left, key); // Recursively delete in left subtree
} else if (key > node->data) {
node->right = delete_node(node->right, key); // Recursively delete in right subtree
} else {
// Node to be deleted is found
if (node->left == nullptr) {
Node* temp = node->right;
delete node; // Delete the node and return its right subtree
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node; // Delete the node and return its left subtree
return temp;
}
// Node has two children, find the inorder successor
Node* temp = find_min(node->right);
node->data = temp->data; // Copy the inorder successor's value to this node
node->right = delete_node(node->right, temp->data); // Delete the inorder successor
}
return node;
}
// Helper function to perform inorder traversal
void inorder(Node* node) {
if (node == nullptr) {
return;
}
inorder(node->left); // Visit left subtree
cout << node->data << " "; // Visit node
inorder(node->right); // Visit right subtree
}
public:
// Constructor to initialize an empty BST
binary_search_tree() {
root = nullptr;
}
// Public insert function
void insert(int data) {
root = insert(root, data);
}
// Public search function
bool search(int key) {
return search(root, key);
}
// Public delete function
void delete_node(int key) {
root = delete_node(root, key);
}
// Public inorder traversal function
void inorder() {
inorder(root);
cout << endl;
}
};
int main() {
binary_search_tree bst;
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
cout << "Inorder traversal: ";
bst.inorder();
cout << "Search for 40: " << (bst.search(40) ? "Found" : "Not Found") << endl;
cout << "Search for 100: " << (bst.search(100) ? "Found" : "Not Found") << endl;
bst.delete_node(20); // Delete a leaf node
cout << "Inorder traversal after deleting 20: ";
bst.inorder();
bst.delete_node(30); // Delete a node with one child
cout << "Inorder traversal after deleting 30: ";
bst.inorder();
bst.delete_node(50); // Delete a node with two children
cout << "Inorder traversal after deleting 50: ";
bst.inorder();
return 0;
}
Output:
2. Validate if a Tree is a Binary Search Tree
This program validates whether a binary tree is a Binary Search Tree (BST) by recursively checking that each node's value lies within an allowable range. The is_valid_bst function ensures that all values in the left subtree are less than the current node and all values in the right subtree are greater, updating these constraints as it traverses the tree. The is_bst function acts as a wrapper, initiating the validation process with the full range of possible values.
Code:
#include <iostream>
#include <climits>
using namespace std;
// Define the structure for a node in the binary tree
struct Node {
int data;
Node* left;
Node* right;
// Constructor to initialize a node
Node(int value) {
data = value;
left = right = nullptr;
}
};
// Function to validate if a binary tree is a BST
bool is_valid_bst(Node* node, long long minValue, long long maxValue) {
if (node == nullptr) {
return true; // An empty tree is a valid BST
}
// Check the current node's value is within the valid range
if (node->data <= minValue || node->data >= maxValue) {
return false;
}
// Recursively check the left and right subtrees with updated constraints
return is_valid_bst(node->left, minValue, node->data) && is_valid_bst(node->right, node->data, maxValue);
}
// Wrapper function to validate if the binary tree is a BST
bool is_bst(Node* root) {
return is_valid_bst(root, LLONG_MIN, LLONG_MAX);
}
int main() {
Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(20);
root->left->left = new Node(1);
root->left->right = new Node(8);
root->right->left = new Node(15);
root->right->right = new Node(25);
if (is_bst(root)) {
cout << "The tree is a valid Binary Search Tree." << endl;
} else {
cout << "The tree is NOT a valid Binary Search Tree." << endl;
}
return 0;
}
Output:
3. Find the Kth Smallest / Largest Element in a BST
This program finds the kth smallest and kth largest elements in a Binary Search Tree (BST) using recursive inorder and reverse inorder traversals, respectively. The kth_smallest function traverses the left subtree, processes the current node, and then the right subtree, decrementing k at each step until the kth smallest element is found. Similarly, kth_largest processes the right subtree first, then the current node, and finally the left subtree to locate the kth largest element.
Code:
#include <iostream>
using namespace std;
// Define the structure for a node in the BST
struct Node {
int data;
Node* left;
Node* right;
// Constructor for initializing a node
Node(int value) {
data = value;
left = right = nullptr;
}
};
// Function to find the kth smallest element in BST
void kth_smallest(Node* root, int& k, int& result) {
if (root == nullptr || k <= 0) {
return;
}
// Traverse the left subtree first (inorder traversal)
kth_smallest(root->left, k, result);
// Decrease k for the current node
k--;
// If k becomes 0, we've found the kth smallest element
if (k == 0) {
result = root->data;
return;
}
// Traverse the right subtree
kth_smallest(root->right, k, result);
}
// Function to find the kth largest element in BST
void kth_largest(Node* root, int& k, int& result) {
if (root == nullptr || k <= 0) {
return;
}
// Traverse the right subtree first (reverse inorder traversal)
kth_largest(root->right, k, result);
// Decrease k for the current node
k--;
// If k becomes 0, we've found the kth largest element
if (k == 0) {
result = root->data;
return;
}
// Traverse the left subtree
kth_largest(root->left, k, result);
}
int main() {
Node* root = new Node(50);
root->left = new Node(30);
root->right = new Node(70);
root->left->left = new Node(20);
root->left->right = new Node(40);
root->right->left = new Node(60);
root->right->right = new Node(80);
int k = 3;
int result = -1;
kth_smallest(root, k, result);
cout << "The 3rd smallest element is: " << result << endl;
k = 3;
result = -1;
kth_largest(root, k, result);
cout << "The 3rd largest element is: " << result << endl;
return 0;
}
Output:
4. Find the Floor and Ceil of a Given Key in a BST
This program finds the floor and ceil of a given key in a Binary Search Tree (BST). The find_floor function traverses the tree, updating the floor to the largest value less than or equal to the key while moving to the right for larger values. Similarly, the find_ceil function updates the ceil to the smallest value greater than or equal to the key while moving to the left for smaller values. Both functions stop traversal once the appropriate value is found.
Code:
#include <iostream>
using namespace std;
// Define the structure for a node in the BST
struct Node {
int data;
Node* left;
Node* right;
// Constructor for initializing a node
Node(int value) {
data = value;
left = right = nullptr;
}
};
// Function to find the floor of a key in the BST
int find_floor(Node* root, int key) {
int floor = -1; // Initialize floor as -1 (indicating no floor found)
while (root != nullptr) {
if (root->data == key) {
return root->data; // If key matches, it is its own floor
} else if (key > root->data) {
floor = root->data; // Update floor to current node value
root = root->right; // Move to the right subtree
} else {
root = root->left; // Move to the left subtree
}
}
return floor;
}
// Function to find the ceil of a key in the BST
int find_ceil(Node* root, int key) {
int ceil = -1; // Initialize ceil as -1 (indicating no ceil found)
while (root != nullptr) {
if (root->data == key) {
return root->data; // If key matches, it is its own ceil
} else if (key < root->data) {
ceil = root->data; // Update ceil to current node value
root = root->left; // Move to the left subtree
} else {
root = root->right; // Move to the right subtree
}
}
return ceil;
}
int main() {
Node* root = new Node(50);
root->left = new Node(30);
root->right = new Node(70);
root->left->left = new Node(20);
root->left->right = new Node(40);
root->right->left = new Node(60);
root->right->right = new Node(80);
int key = 65;
int floor = find_floor(root, key);
int ceil = find_ceil(root, key);
cout << "The floor of " << key << " is: " << (floor == -1 ? "None" : to_string(floor)) << endl;
cout << "The ceil of " << key << " is: " << (ceil == -1 ? "None" : to_string(ceil)) << endl;
return 0;
}
Output:
5. Convert a BST to a Sorted Doubly Linked List
This program converts a Binary Search Tree (BST) into a sorted doubly linked list using an inorder traversal. The recursive function bst_to_doubly_ll visits nodes in sorted order, linking each node to its predecessor via the left pointer and to its successor via the right pointer. A head pointer tracks the start of the list, and a prev pointer maintains the previously visited node.
Code:
#include <iostream>
using namespace std;
// Define the structure for a node in the BST
struct Node {
int data;
Node* left;
Node* right;
// Constructor for initializing a node
Node(int value) {
data = value;
left = right = nullptr;
}
};
// Helper function to convert BST to a sorted doubly linked list
void bst_to_doubly_ll(Node* root, Node*& head, Node*& prev) {
if (root == nullptr) {
return; // Base case: empty subtree
}
// Recursively convert the left subtree
bst_to_doubly_ll(root->left, head, prev);
// Process the current node
if (prev == nullptr) {
head = root; // This is the leftmost (smallest) node
} else {
prev->right = root; // Link the previous node to the current node
root->left = prev; // Link the current node back to the previous node
}
prev = root; // Update the previous node to the current node
// Recursively convert the right subtree
bst_to_doubly_ll(root->right, head, prev);
}
// Function to convert BST to sorted doubly linked list
Node* convert_to_doubly_ll(Node* root) {
Node* head = nullptr; // Pointer to the head of the doubly linked list
Node* prev = nullptr; // Pointer to keep track of the previous node
bst_to_doubly_ll(root, head, prev);
return head;
}
// Function to print the doubly linked list
void print_doubly_ll(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->right;
}
cout << endl;
}
int main() {
Node* root = new Node(50);
root->left = new Node(30);
root->right = new Node(70);
root->left->left = new Node(20);
root->left->right = new Node(40);
root->right->left = new Node(60);
root->right->right = new Node(80);
Node* head = convert_to_doubly_ll(root);
cout << "The sorted doubly linked list is: ";
print_doubly_ll(head);
return 0;
}
Output:
Day 20 highlighted the efficiency and adaptability of Binary Search Trees in managing and querying dynamic data. By exploring fundamental operations and advanced problem-solving techniques, today’s challenges reinforced the importance of mastering BSTs for efficient algorithm design. 🚀