BINARY SEARCH TREE

BINARY SEARCH TREE

What Is Binary Search Tree?

A binary search tree (BST) is a type of data structure that allows for fast insertion, deletion, and searching of data. It is called a "binary" search tree because each node has at most two children.

At the root of the tree, the left child node contains a value less than its parent node, and the right child node contains a value greater than its parent node. This pattern is then repeated for each level of the tree, with the left child nodes always containing a value less than their parent node and the right child nodes containing a value greater than their parent node.

One of the main advantages of a BST is that it allows for efficient searching of data. To search or a specific value in a BST, you start at the root node and compare the value you are searching for with the value at the current node. If the value you are searching for is less than the value at the current node, you move to the left child node. If the value you are searching for is greater than the value at the current node, you move to the right child node. This process continues until you either find the value you are searching for or you reach a leaf node (a node with no children).

Insertion and deletion in a BST is also relatively efficient. To insert a new value into a BST, you simply follow the same process as searching for a value, but instead of stopping when you find the value you are searching for, you continue until you reach a leaf node. At this point, you can insert the new value as a child of the leaf node.

Deletion in a BST is a bit more complicated. 

There are three main cases to consider when deleting a node from a BST:

1. The node to be deleted is a leaf node. In this case, the deletion process is straightforward. Simply remove the node from the tree and update the parent node to no longer point to the deleted node.
2. The node to be deleted has one child. In this case, you can simply remove the node and replace it with its child.
3. The node to be deleted has two children. In this case, the process becomes a bit more complicated. One solution is to find the in order successor (the next largest value in the BST) of the node to be deleted and replace the node with its in order successor. The in order successor can then be removed using one of the first two cases.