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.