Binary Search Tree (BST)
Written by
What is Binary Search Tree (BST)?
A binary search tree or BST is a binary tree in which for each node in the tree, elements in the left subtree are less than the root node and elements on the right are equal or greater than the root node.
The common operations performed on a BST are
- Searching—Search for a specific item in the tree
- Insertion—An item needs to be inserted
- Deletion—Deleting a node from a tree
A binary search tree T is in memory and ITEM is the element to be found. LOC is the location of the ITEM in T and PAR is the location of the parent.
# Four cases could be possible
- LOC=NULL and PAR=NULL meaning tree is empty.
- LOC≠NULL and PAR=NULL meaning ITEM is the root of T.
- LOC=NULL and PAR≠NULL means ITEM is not in the T
- LOC≠NULL and PAR≠NULL means ITEM already exists in T.
# Discussing operations in detail
Searching
Searching, as the name literally mean finds an item in the BST.
We start searching from the root and move downward towards left or right. The item is compared with the root node and then moved to an appropriate subtree (left or right). If it matches the node value, the search is successful and the address of the node is returned.
If the value is less than the root node, it searches in the left tree else it moves to the right tree. If the value is not found in the tree, the search becomes unsuccessful and returns Null.
Insertion
Insertion, Binary Search tree formation is basically repeated insertion of items in the tree. In a BST, the item moves towards the left if it is of lesser value than the root node and on the right side if we have nodes with the values equal or greater than the root node.
Deletion
Deletion, the deletion process will first find the item needed to be deleted. There could be three cases in deletion.
- When parent node N has no child: the targeted node is simply deleted.
- Parent node N has only one child: the targeted node is deleted and replaced by its child node.
- Parent node N has two children: it is a little complicated than the above two deletions. Anyways, let’s understand.
Suppose, node N is to be deleted then we traverse and look for the minimum value node in the right side of the tree and replace the deleted node with this “minimum value” node.
