Binary Search Trees (BST)
Description
Binary Search Trees (BST) are binary trees that follow the properties of the binary search algorithm. Each node has a key value and left and right subtrees where the left subtree contains only nodes with keys lesser than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. This organization allows for efficient search, insertion, and deletion operations.
C++ Code
#include <iostream>
using namespace std;
struct TreeNode {
int key;
TreeNode* left;
TreeNode* right;
TreeNode(int k) : key(k), 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;
}
bool search(TreeNode* root, int key) {
if (root == nullptr || root->key == key) {
return root != nullptr;
}
if (key < root->key) {
return search(root->left, key);
}
return search(root->right, key);
}
public:
BST() : root(nullptr) {}
void insert(int key) {
root = insert(root, key);
}
bool search(int key) {
return search(root, key);
}
};
int main() {
BST bst;
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
cout << "Search 60: " << (bst.search(60) ? "Found" : "Not found") << endl;
cout << "Search 90: " << (bst.search(90) ? "Found" : "Not found") << endl;
return 0;
}
Time and Space Complexity
| Operation | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity |
|---|---|---|---|
| Insertion | O(log n) | O(n) | O(n) |
| Deletion | O(log n) | O(n) | O(n) |
| Search | O(log n) | O(n) | O(1) |
Where:
- n: Number of nodes in the binary search tree.