Binary Search Tree (BST)

A Binary Search Tree (BST) is a type of data structure used in programming to

store data in an organized way. It allows us to search, insert, and delete data
efficiently. Let’s break it into simple parts.

Properties of a Binary Search Tree

1. Nodes: A BST is made of nodes. Each node has three parts:

o A value (data).
o A link to the left child (smaller value).
o A link to the right child (greater value).
2. Left Child: Every value in the left child of a node is smaller than

You said:
Not short

ChatGPT said:
ChatGPT

Binary Search Tree (BST) in DSA with C++

A Binary Search Tree (BST) is a tree-based data structure where each node has at
most two child nodes, referred to as the left child and the right child. It’s widely
used in programming because it organizes data in a way that makes searching,
inserting, and deleting efficient.

Properties of a Binary Search Tree

1. Binary Structure: Each node in the tree has at most two children: a left child and a right
child.
2. Order Property:
o Left Subtree: All values in the left subtree of a node are smaller than the node’s
value.
o Right Subtree: All values in the right subtree of a node are greater than the
node’s value.
3. Unique Values: Typically, a BST does not allow duplicate values.
4. Recursive Structure: Each subtree of a BST is also a BST.
Basic Terminology

1. Node: The basic unit of a tree that contains a value and pointers to children.
2. Root: The topmost node in the tree.
3. Leaf: A node with no children.
4. Parent: A node that has child nodes.
5. Child: A node connected to a parent.
6. Subtree: A smaller tree inside the main tree.
7. Height: The number of edges on the longest path from the root to a leaf.

Operations in Binary Search Tree (7 Operations)

1. Creation of a BST
o Start by creating a root node.
o Add new values by comparing them with existing nodes:
 If smaller, go to the left.
 If larger, go to the right.
o Example in C++:

cpp
Copy code
struct Node {
int value;
Node* left;
Node* right;
Node(int val) : value(val), left(nullptr),
right(nullptr) {}
};

Node* insert(Node* root, int value) {

if (root == nullptr) return new Node(value);
if (value < root->value) root->left = insert(root-
>left, value);
else root->right = insert(root->right, value);
return root;
}

2. Traversal of a BST
Traversing means visiting each node. There are three main types of
traversal:
o Inorder (Left, Root, Right): Gives sorted values in ascending order.
o Preorder (Root, Left, Right): Useful for creating copies of trees.
 o Postorder (Left, Right, Root): Useful for deleting a tree.
Example of Inorder Traversal:

cpp
Copy code
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}

3. Search Operation
o Start at the root and compare the target value with the node's value.
o Move left if the target is smaller; move right if it’s larger.
o Stop when the value is found or when a leaf node is reached.
Example:

cpp
Copy code
bool search(Node* root, int key) {
if (root == nullptr) return false;
if (root->value == key) return true;
return key < root->value ? search(root->left, key) :
search(root->right, key);
}

4. Insertion
o Follow the same steps as in search to find the correct position for the new value.
o Create a new node and attach it.
5. Deletion
o Three cases:
1. Node has no children (a leaf node): Simply delete it.
2. Node has one child: Replace the node with its child.
3. Node has two children: Replace the node with its inorder successor
(smallest value in the right subtree).
Example:

cpp
Copy code
Node* deleteNode(Node* root, int key) {
if (root == nullptr) return root;
if (key < root->value) root->left = deleteNode(root->left,
key);
else if (key > root->value) root->right = deleteNode(root-
>right, key);
else {
 if (root->left == nullptr) return root->right;
if (root->right == nullptr) return root->left;
Node* temp = root->right;
while (temp->left != nullptr) temp = temp->left;
root->value = temp->value;
root->right = deleteNode(root->right, temp->value);
}
return root;
}

6. Finding Minimum and Maximum Values

o Minimum: Go left until there are no more left children.
o Maximum: Go right until there are no more right children.
Example:

cpp
Copy code
int findMin(Node* root) {
while (root->left != nullptr) root = root->left;
return root->value;
}

7. Finding Height of the Tree

o Height is the longest path from the root to any leaf.
Example:

cpp
Copy code
int height(Node* root) {
if (root == nullptr) return -1;
return 1 + max(height(root->left), height(root->right));
}

Applications of Binary Search Tree

1. Searching and Sorting: BST makes searching and sorting efficient, especially for dynamic
data.
2. Database Indexing: Used to quickly retrieve records.
3. Routing Tables: Used in network routing algorithms.
4. Auto-complete Suggestions: BST helps in implementing prefix-based searches.
5. Mathematical Expression Parsing: Used in compilers to parse mathematical
expressions.
6. File Systems: Some file systems use BST for organizing files.
7. Dynamic Sets: Useful in scenarios where data is frequently inserted or deleted.
Summary

A BST is an efficient data structure for operations like searching, insertion, and
deletion. Understanding its properties, operations, and applications helps solve
many real-world problems in programming.