Day 20: 100 Days of DSA

Welcome to Day 20 of my 100 Days of DSA challenge! Today, I solved five problems focused on basics of binary trees. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

1. Implement a binary search tree with insertion, deletion, and search operations.

A Binary Search Tree (or BST) is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.

Code:

// To implement a binary search tree and perform insertion, deletion.

#include<iostream>
using namespace std;

class Node{
    public:
     int data;
     Node* left;
     Node* right;

     Node(int data){
        this->data=data;
        this->left=NULL;
        this->right=NULL;
     }
};

Node* insert(Node* node,int key){
     if (node == NULL) 
        return new Node(key); 
     if (node->data == key) 
        return node;
     if (node->data < key) 
        node->right = insert(node->right, key);
     else 
        node->left = insert(node->left, key);
    return node;
}


void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

int main(){
    Node* root = new Node(50);
    cout<<"Inserting nodes..."<<endl;
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    cout<<"The inorder traversal is:"<<endl;
    inorder(root);

}

Output:

2. Solve the "validate if a tree is a binary search tree" problem.

• The function isBSTUtil recursively validates if each node adheres to the BST property by checking its value against a range.

• Each node's left subtree values must be less than the node's value, and right subtree values must be greater.

INT_MIN and INT_MAX are used to initialize the range, ensuring all nodes are evaluated properly.

Code:

#include <iostream>
#include <climits>
using namespace std;

class Node{
    public:
     int data;
     Node* left;
     Node* right;

     Node(int data){
        this->data=data;
        this->left=NULL;
        this->right=NULL;
     }
};
bool isBSTUtil(Node* root, int minVal, int maxVal) {
    if (!root) return true;
    if (root->data <= minVal || root->data >= maxVal) return false;
    return isBSTUtil(root->left, minVal, root->data) && isBSTUtil(root->right, root->data, maxVal);
}

bool isBST(Node* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(2);
    root->left->right = new Node(7);

    if (isBST(root))
        cout << "The tree is a valid BST." << endl;
    else
        cout << "The tree is not a valid BST." << endl;
    return 0;
}

Output:

3. Solve the "find the kth smallest/largest element in a BST" problem.

• An in-order traversal is used to process nodes in ascending order for a BST.

• A counter k is decremented during traversal, and when it reaches 0, the current node is the kth smallest.

• The function is efficient and directly halts traversal when the kth smallest is found.

• Using struct this time instead of class, just for a change :)

Code:

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    Node(int val) : key(val), left(nullptr), right(nullptr) {}
};

void inorderTraversal(Node* root, int& k, int& result) {
    if (!root || k <= 0) return;
    inorderTraversal(root->left, k, result);
    k--;
    if (k == 0) {
        result = root->key;
        return;
    }
    inorderTraversal(root->right, k, result);
}

int kthSmallest(Node* root, int k) {
    int result = -1;
    inorderTraversal(root, k, result);
    return result;
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(2);
    root->left->right = new Node(7);

    int k = 3;
    cout << "The " << k << "rd smallest element is: " << kthSmallest(root, k) << endl;
    return 0;
}

Output:

4. Solve the "find the floor and ceil of a given key in a BST" problem.

• The Node class represents a node with key, left, and right pointers.

• The BST class contains the root pointer and methods for insertion, floor, and ceil finding.

• The findFloor and findCeil methods iteratively traverse the BST to determine the largest value ≤ key (floor) and the smallest value ≥ key (ceil).

Code:

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node* left;
    Node* right;
    Node(int val) : key(val), left(nullptr), right(nullptr) {}
};

class BST {
public:
    Node* root;
    BST() : root(nullptr) {}

    void insert(int key) {
        root = insertRec(root, key);
    }

    int findFloor(int key) {
        return findFloorRec(root, key);
    }

    int findCeil(int key) {
        return findCeilRec(root, key);
    }

private:
    Node* insertRec(Node* root, int key) {
        if (!root) return new Node(key);
        if (key < root->key)
            root->left = insertRec(root->left, key);
        else
            root->right = insertRec(root->right, key);
        return root;
    }

    int findFloorRec(Node* root, int key) {
        int floor = -1;
        while (root) {
            if (root->key == key) return root->key;
            if (root->key < key) {
                floor = root->key;
                root = root->right;
            } else {
                root = root->left;
            }
        }
        return floor;
    }

    int findCeilRec(Node* root, int key) {
        int ceil = -1;
        while (root) {
            if (root->key == key) return root->key;
            if (root->key > key) {
                ceil = root->key;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return ceil;
    }
};

int main() {
    BST tree;
    tree.insert(8);
    tree.insert(4);
    tree.insert(12);
    tree.insert(2);
    tree.insert(6);
    tree.insert(10);
    tree.insert(14);

    int key = 5;
    cout << "Floor of " << key << " is: " << tree.findFloor(key) << endl;
    cout << "Ceil of " << key << " is: " << tree.findCeil(key) << endl;

    return 0;
}

Output:

5. Solve the "convert a BST to a sorted doubly linked list" problem.

• This converts a BST into a sorted doubly linked list using an in-order traversal.

• The convertRec function connects nodes as it traverses, maintaining prev as the last processed node and head as the list's head.

• The linked list's nodes are connected by modifying the left and right pointers.

Code:

#include <iostream>
using namespace std;

class Node {
public:
    int key;
    Node* left;
    Node* right;
    Node(int val) : key(val), left(nullptr), right(nullptr) {}
};

class BST {
public:
    Node* root;
    BST() : root(nullptr) {}

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node* convertToDoublyLinkedList() {
        Node* head = nullptr, *prev = nullptr;
        convertRec(root, prev, head);
        return head;
    }

private:
    Node* insertRec(Node* root, int key) {
        if (!root) return new Node(key);
        if (key < root->key)
            root->left = insertRec(root->left, key);
        else
            root->right = insertRec(root->right, key);
        return root;
    }

    void convertRec(Node* root, Node*& prev, Node*& head) {
        if (!root) return;
        convertRec(root->left, prev, head);
        if (!prev) head = root;
        else {
            prev->right = root;
            root->left = prev;
        }
        prev = root;
        convertRec(root->right, prev, head);
    }
};

void printList(Node* head) {
    Node* temp = head;
    while (temp) {
        cout << temp->key << " ";
        temp = temp->right;
    }
    cout << endl;
}

int main() {
    BST tree;
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(2);
    tree.insert(7);

    Node* head = tree.convertToDoublyLinkedList();
    printList(head);

    return 0;
}

Output:

This is all for today! See ya tomorrow :)