Binary Search Tree (BST) Guide
1. Introduction to Binary Search Trees (BST)
A Binary Search Tree (BST) is a binary tree with the following properties:
- Each node has at most two children, referred to as the left child and the right child.
- For each node, all nodes in its left subtree have values less than the node's value,
and all nodes in its right subtree have values greater than the node's value.
BSTs are used for fast data retrieval, with time complexity O(log n) for balanced trees.
2. BST Operations
BST supports operations like Insertion, Deletion, Searching, and Traversal. Let's cover each:
- **Insertion**: Insert a node such that the BST property is maintained.
- **Searching**: Check if a value exists in the BST.
- **Deletion**: Remove a node and maintain the BST property.
- **Traversal**: Visit nodes in a specific order (Inorder, Preorder, Postorder).
Insertion Code Example
void insert(Node* &root, int value) {
if (root == NULL) {
root = new Node(value);
return;
Binary Search Tree (BST) Guide
if (value < root->data) {
insert(root->left, value);
} else {
insert(root->right, value);
Search Code Example
bool search(Node* root, int value) {
if (root == NULL) return false;
if (root->data == value) return true;
if (value < root->data) return search(root->left, value);
return search(root->right, value);
Deletion Code Example
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
Binary Search Tree (BST) Guide
root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) return root->right;
else if (root->right == NULL) return root->left;
root->data = minValue(root->right);
root->right = deleteNode(root->right, root->data);
return root;
Traversal Code Examples
// Inorder Traversal
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
// Preorder Traversal
void preorder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
Binary Search Tree (BST) Guide
preorder(root->left);
preorder(root->right);
// Postorder Traversal
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
Summary of Key Points
- **BST** is a binary tree where the left child is less than the parent node, and the right child is greater.
- **Operations**: Insertion, Deletion, Searching, and Traversal.
- **Traversals**:
- Inorder (Left, Root, Right) - returns sorted order in BST.
- Preorder (Root, Left, Right) - useful for copying trees.
- Postorder (Left, Right, Root) - used in deleting or freeing nodes.
