Binary Search Tree in data structure.
Practice problem on Binary Search Tree
Learn Binary Search Tree
Binary search tree can be defined as a class of binary tree, in which the nodes are arranged in a specific order. It is also called ordered binary tree.
In a binary search tree, the value of all nodes in the left sub-tree is less than the value of the root.
Similarly, the value of all nodes in the right sub-tree is greater than or equal to the value of the root.
This rule will be reapplied to all left and right sub-trees of root.
Binary search tree is a special type of binary tree which can be defined as Class. In which the nodes are arranged in a specific order.
All the information in the left sub tree is smaller than the root and all the information in the right sub tree is bigger than the root.
Right sub – The value of all nodes in the tree is greater than or equal to the value of the root.
Both left and right are sub binary search trees.
Advantages of using binary search tree
Searching in binary search tree becomes very efficient, we get a hint at each step about which sub-tree contains the desired element.
Binary search tree is considered to be efficient data structure as compared to arrays and linked lists. In the search process, it removes half the sub-tree at each step. Searching for an element in a binary search tree takes o(log2n) time. In the worst case, the time taken to find an element is 0(n).
It also speeds up the insertion and deletion tasks as compared to arrays and linked lists.
Operations on Binary Search Tree
There are many operations that can be performed on binary search.
Operation Description
1 Searching in BST To find the location of some specific element in binary search tree.
2 Inserting in BST Adding a new element to the binary search tree at the appropriate place so that the property of BST is not violated.
3 Deletion in BST Binary search tree to remove some specific node. However, depending on the number of children, there may be different cases of deletion.
Adding a node to the binary search tree ( Insertion )
For this, first we send a temporary variable T to root and a variable Prev to NULL.
Prev variable will display the node before T, now we will allocate memory to a new node.
Will insert data in its information part and NULL value in left and right.
After this Prev will be sent to T through the loop and it will be checked whether the value of data is smaller than the value of T.
If the value of data is less than T then it will be inserted to the left of T.
If the value of data is greater than T then it will be inserted to the right of T.
Now we will check that the previous variable which is representing the previous node of T.
NULL is not. If NULL is there then the tree is empty. So the new node will be made root.