Binary Search Tree

Binary Search Tree:

A binary search tree (BST) is a data structure where each node has at most two child nodes: a left child and a right child. The key (value) of nodes in the left subtree is less than the key of the current node, and the key of nodes in the right subtree is greater. This hierarchical structure allows for efficient searching, insertion, and deletion of elements. It’s like organizing data in a way that makes it easy to quickly find what you’re looking for.

#include
class Node {
public:
int key;
Node* left;
Node* right;

Node(int value) {
key = value;
left = right = nullptr;
}
};
class BinarySearchTree {
private:
Node* root;
public:
BinarySearchTree() {
root = nullptr;
}
void insert(int key) {
root = _insert(root, key);
}
Node* _insert(Node* node, int key) {
if (node == nullptr) {
return new Node(key);
}

if (key < node->key) {
node->left = _insert(node->left, key);
} else if (key > node->key) {
node->right = _insert(node->right, key);
}

return node;
}
Node* search(int key) {
return _search(root, key);
}

Node* _search(Node* node, int key) {
if (node == nullptr || node->key == key) {
return node;
}

if (key < node->key) {
return _search(node->left, key);
} else {
return _search(node->right, key);
}
}
};
int main() {
BinarySearchTree bst;
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
// Search for a key
Node* result = bst.search(4);
if (result) {
std::cout << “Key 4 found in the tree.” << std::endl;
} else {
std::cout << “Key 4 not found in the tree.” << std::endl;
}
return 0;
}