height of bst cpp

To find the height of a Binary Search Tree (BST) in C++, you can use the following recursive algorithm:

Step 1: Define the structure for a node in the BST.

struct Node {
    int data;
    Node* left;
    Node* right;
};

Step 2: Implement the function to calculate the height of the BST.

int height(Node* root) {
    if (root == nullptr) {
        return -1; // Base case: an empty tree has height -1
    } else {
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);

        // Return the maximum height between the left and right subtrees, plus 1 for the root
        return 1 + max(leftHeight, rightHeight);
    }
}

Step 3: Call the height() function with the root of the BST to get the height.

Example usage:

int main() {
    // Create a BST
    Node* root = new Node;
    root->data = 5;
    root->left = new Node;
    root->left->data = 3;
    root->left->left = nullptr;
    root->left->right = nullptr;
    root->right = new Node;
    root->right->data = 8;
    root->right->left = nullptr;
    root->right->right = nullptr;

    // Calculate the height
    int bstHeight = height(root);

    // Output the height
    cout << "Height of the BST: " << bstHeight << endl;

    // Clean up memory
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

This example creates a BST with a height of 1. You can modify the values and structure of the BST to test different heights.