Binary
Search Tree:
A Binary Search Tree (BST) is a type of data structure that helps in organizing and managing data efficiently. Here’s a simple explanation of its properties and how it works:
What is a Binary Search Tree?
A Binary Search Tree is a tree structure where each node has at most two children, referred to as the left child and the right child. This type of tree has a specific way of arranging data to make searching, insertion, and deletion operations very efficient.
Properties of a Binary Search Tree
Node Arrangement:
- Each node in a BST contains a key (a value).
- The left subtree of a node contains only nodes with keys that are less than the node’s key.
- The right subtree of a node contains only nodes with keys that are greater than the node’s key.
Subtree Structure:
- Both the left and right subtrees of each node must also be binary search trees. This means the rules for arranging nodes apply to every subtree within the tree.
How Does It Work?
Consider you have a BST, and you want to find a particular value. You start at the root node:
Searching:
- If the value you are searching for is less than the root’s key, you move to the left child.
- If it is greater, you move to the right child.
- You repeat this process until you find the value or reach a leaf node (a node with no children).
Insertion:
- To insert a new value, you follow the same logic as searching.
- Starting at the root, you move left or right depending on whether the new value is less than or greater than the current node’s key.
- When you find an appropriate empty spot (where a child node would be null), you insert the new value there.
Deletion:
- Deleting a node from a BST requires a bit more thought:
- If the node is a leaf, you can simply remove it.
- If the node has one child, you remove the node and replace it with its child.
- If the node has two children, you need to find the in-order successor (the smallest node in the right subtree) or the in-order predecessor (the largest node in the left subtree), replace the node's key with this successor’s (or predecessor’s) key, and then delete the successor (or predecessor)
- Deleting a node from a BST requires a bit more thought:
Inorder Traversal:
At first traverse left subtree then visit the root and then traverse the right subtree.
Follow the below
steps to implement the idea:
·
Traverse left subtree
·
Visit the root and print the data.
·
Traverse the right subtree
Program:
// C++ code to implement the approach
//Inorder
#include <bits/stdc++.h>
using namespace std;
// Class describing a node of tree
class Node {
public:
int data;
Node* left;
Node* right;
Node(int v)
{
this->data = v;
this->left = this->right = NULL;
}
};
// Inorder Traversal
void printInorder(Node* node)
{
if (node ==
NULL)
return;
// Traverse left
subtree
printInorder(node->left);
// Visit node
cout <<
node->data << " ";
// Traverse
right subtree
printInorder(node->right);
}
// Driver code
int main()
{
// Build the
tree
Node* root = new
Node(100);
root->left =
new Node(20);
root->right =
new Node(200);
root->left->left = new Node(10);
root->left->right = new Node(30);
root->right->left = new Node(150);
root->right->right = new Node(300);
// Function call
cout <<
"Inorder Traversal: ";
printInorder(root);
return 0;
}
.png)

.png)
.png)

.png)


.png)
