Binary Search Tree
Binary Seach Tree is the special type of node-based Binary Tree that contains data in an organized way so that basic operations such as insertion, deletion, and searching become easier. It is an ordered and sorted Binary Tree. A binary search tree in the data structure is the most interesting topic to learn. Let us see the implementation of the binary search tree and various operations on it. we will implement BST in the recursive algorithm.
Properties of Binary Search Tree
- Tree Should be a Binary Tree
- Left Subtree Contains a value lower than the parent's value.
- Right Subtree Contains the value greater or equals to the parent's value.
Here is an Example of Binary search tree
Application of Binary search tree
- A binary search tree is used in the implementation of searching algorithms
- A binary search tree is used in Multilevel indexing in a database.
- It is used in the Implementation of TreeMap and TreeSet
- It is used in data compression
- It is helpful in managing memory
- Searching in a Binary search tree is much easier than any other data structure.
Basic Operations on Binary Search Tree (BST)
- INSERTION
- DELETION
- SEARCHING
- MODIFYING
- TRANSVERSAL
The requirement to learn Binary search tree
These are the topic that you should learn before understanding the binary search trees.
- Recursion
- Classes
- Node
INSERTION in Binary Search Tree
Element in Binary Search Tree is Inserted on behalf of some rules which is mentioned earlier. Insertion means adding a new node in the Binary search tree.
Implementation of Binary search tree in Java is similar to another language as C++ and Python
Let us write code for making Node
the complexity of insertion in the Binary search tree is logN.
Code for Node Creation in C++
class Node
{
public:
int data;
Node* left;
Node* right;
Node(int val)
{
data=val;
left=NULL;
right=NULL;
}
};
Code for Node creation in Java
class Node
{
int data;
Node left;
Node right;
public Node(int val)
{
data=val;
left=null;
right=null;
}
}
Insertion in Binary Search Tree
we will make an Insert function to insert an element in the Binary Search Tree at its appropriate position. we will recursively iterate through either left or right of the root node to find its appropriate position for insertion.
Insertion in Binary search tree in C++
Node* inserts(Node* root, int val)
{
if(root==NULL)
{
Node* a = new Node(val);
root=a;
return root;
}
else if(val<root->data)
{
root->left=inserts(root->left,val);
}
else
{
root->right=inserts(root->right,val);
}
return root;
}
Insertion in Binary Search Tree in Java
Node insert(Node root, int val)
{
if(root==null)
{
root=new Node(val);
return root;
}
if(val<root.val)
{
root.left=insert(root.left,val);
}
else
{
root.right=insert(root.right,val);
}
return root;
}
InOrder Transversal in Binary Search Tree
In order transversal in Binary Search Tree gives elements in Ascending order. In this left subtree is visited first and then the right tree for accessing elements of all nodes.
Code in C++
void Inorder(Node* root)
{
Node* temp=root;
if(temp==NULL) return;
Inorder(root->left);
cout<<temp->data<<"\n";
Inorder(root->right);
}
Code in Java
void Inorder(Node* root)
{
Node* temp=root;
if(temp==NULL) return;
Inorder(root->left);
cout<<temp->data<<"\n";
Inorder(root->right);
}
We have discussed the Insertion of data in Binary Search Tree (BST) and Inorder Transversal in Binary search Tree. One of the major disadvantages of a Binary search tree is that it requires a recursive approach for its implementation which is sometimes more complex to write.
we prefer Binary Search Over any Other Data Structure because it is very efficient and less complex to perform basic operations such as searching and deletion. In Further Blogs, we will discuss How to Delete elements from the Binary Search tree. This is a very important topic for coding interviews and competitive programming.
