Analysis of Binary Search Tree
It is very hard to find a simple and an easy explanation about Binary Search Tree.Quite a number of times, we will end up in frustration.I knew this, because I tried to find out in many attempts and got a picture of it 📸.
In this article, I will focus on:
- What is a Tree?
- What is a Binary Tree?
- How the information is saved in a Binary Tree?
- How insertion happens in a BST?
- In-order Traversal
- Benefits of BST.
What is a Tree?
A tree is a typical wood or a trunk which will have branches. Most of the branches will have leaves. Likewise, a Tree in data is a Trunk which we denote as root. Its branches are termed as sub-trees or nodes.
What is a Binary Tree?
A Binary tree is a tree in which nodes can have a maximum of 2 sub trees usually referred as left child and right child. Refer below image for a clear understanding.
Below is the code snippet for creation of a Node:
public class Node {
int data;
Node left,right;
Node(int key){
data=key;
left=right=null;
}
}How the information is cached in a Binary Tree?
Each node is associated with a value. If a node doesn’t have value, it does not exist at all. Because of the fact that nodes are not allowed to be empty.
How insertion happens in a BST?
It is very simple to insert the values in a Binary Tree.If the value to be inserted is less then insertion takes place on the left side. Else, if the value to be inserted in greater, then insertion takes place on the right side.
An important check that has to be carried out while insertion is duplicacy. BST cannot have duplicate entries. In order to prevent this, we need to ensure that the value to be inserted is not equal to the node that is present already.
Refer the below Code snippet for clear explanation:
//Recursive function to insert values in BST
public static Node insertKey(Node root, int value) {
//If the root is found to be null, (i.e)node doesn't exists. Hence we are creating a new node
if (root == null) {
return new Node(value);
}
//Check for the duplicacy of the data in BST.
if (value == root.data) {
return root;
}
// If the value to be inserted is less than the root data, then go left and insert
if (value < root.data) {
root.left = insertKey(root.left, value);
}
// Else If the value to be inserted is greater than the root data, then go right and insert
else if (value > root.data) {
root.right = insertKey(root.right, value);
}
return root;
}Tree Traversal:
There are 3 ways of traversing a tree:
- Inorder(Left,Root,Right)
- Preorder(Root,Left,Right)
- Postorder(Left,Right,Root
Here we are going to see how Inorder traversal works.
- In the first step, traversal of left sub-tree happens recursively.
- Visit and display the root node
- Finally traversal of right sub-tree happens recursively.
Below code snippet throws some light on the above theoretical explanation.
//Recursive function for Inorder traversal.
// Here , traversal is done on the left subtree completely,-> visit the root -> traversal is done on the right subtree completely
// On reaching null values, entry is deleted in the call stack and
// points to the root value previously invoked and the process continues
public static void inOrder(Node root){
if(root==null){
return;
}
inOrder(root.left);
System.out.println(root.data+" ");
inOrder(root.right);
}Please refer here for getting more grasp on the same.
Benefits of BST:
Searching an element in an efficient way will be our top priority at all times. Binary search tree provides an efficient solution where we get a hint at each step about which sub-tree contains the required element. Insertion , deletion and searching is faster when compared to other data structures like arrays and linked lists.
And yess, We are done !
We will explore more on Binary Search Tree operations and other traversal ways in next article!!
Hope this article has been useful for understanding about Binary Search Tree!
A complete repository can be found here!
Do visit my YouTube channel and subscribe for interesting tech videos!🔄
