Untitled

 avatar
unknown
c_cpp
a year ago
4.2 kB
3
Indexable
#include <iostream>
#include <algorithm>
using namespace std;

class TreeNode
{
public:
    int key;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int val) : key(val), left(nullptr), right(nullptr) {}
};

class BST
{
private:
    TreeNode *root;

    TreeNode *insert(TreeNode *root, int key)
    {
        if (root == nullptr)
        {
            return new TreeNode(key);
        }

        if (key < root->key)
        {
            root->left = insert(root->left, key);
        }
        else if (key > root->key)
        {
            root->right = insert(root->right, key);
        }

        return root;
    }

    TreeNode *deleteNode(TreeNode *root, int key)
    {
        if (root == nullptr)
        {
            return root;
        }

        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)
            {
                TreeNode *temp = root->right;
                delete root;
                return temp;
            }
            else if (root->right == nullptr)
            {
                TreeNode *temp = root->left;
                delete root;
                return temp;
            }

            root->key = getMinValue(root->right);
            root->right = deleteNode(root->right, root->key);
        }

        return root;
    }

    int getMinValue(TreeNode *root)
    {
        while (root->left != nullptr)
        {
            root = root->left;
        }
        return root->key;
    }

    void inorderTraversal(TreeNode *root)
    {
        if (root != nullptr)
        {
            inorderTraversal(root->left);
            cout << root->key << " ";
            inorderTraversal(root->right);
        }
    }

    void preorderTraversal(TreeNode *root)
    {
        if (root != nullptr)
        {
            cout << root->key << " ";
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
    }

    void postorderTraversal(TreeNode *root)
    {
        if (root != nullptr)
        {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            cout << root->key << " ";
        }
    }

    int maxDepth(TreeNode *root)
    {
        if (root == nullptr)
        {
            return 0;
        }

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return 1 + max(leftDepth, rightDepth);
    }

    int minDepth(TreeNode *root)
    {
        if (root == nullptr)
        {
            return 0;
        }

        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);

        return 1 + min(leftDepth, rightDepth);
    }

public:
    BST() : root(nullptr) {}

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

    void deleteNode(int key)
    {
        root = deleteNode(root, key);
    }

    void inorderTraversal()
    {
        cout << "In-order Traversal: ";
        inorderTraversal(root);
        cout << endl;
    }

    void preorderTraversal()
    {
        cout << "Pre-order Traversal: ";
        preorderTraversal(root);
        cout << endl;
    }

    void postorderTraversal()
    {
        cout << "Post-order Traversal: ";
        postorderTraversal(root);
        cout << endl;
    }

    int getMaxDepth()
    {
        return maxDepth(root);
    }

    int getMinDepth()
    {
        return minDepth(root);
    }
};

int main()
{
    BST bst;

    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);
    bst.insert(10);

    bst.inorderTraversal();
    bst.preorderTraversal();
    bst.postorderTraversal();

    cout << "Maximum Depth: " << bst.getMaxDepth() << endl;
    cout << "Minimum Depth: " << bst.getMinDepth() << endl;
    cout << " " << endl; 

    bst.deleteNode(10);
    cout << "Traversal after deleting 10: " << endl;
    bst.inorderTraversal();
    bst.preorderTraversal();
    bst.postorderTraversal();

    return 0;
}
Editor is loading...
Leave a Comment