A binary search tree is similar to a binary tree, each node can contain a left and right child and a data field. The parent node is also called the root and the nodes with no children are called leaves.

An important distinction between BST and binary trees is that BSTs are ordered, allowing you to perform a binary search on them and make finding an element more efficient. If a node is greater than another node, it will be to the right of it, otherwise it will be to the left. When you insert a node, instead of adding it to the next open spot, it will add the element based on its value. When deleting a node, it will replace the node by its successor.

Insertion

Compare the data to be added to the root, if it is greater that the root go down the right subtree, else go down the left subtree

Repeat for all the nodes until you find the place where it needs to be inserted

Deletion

Node to be deleted is a leaf - sever it

Node has one child, copy data, delete child

Node has two children, replace it with its inorder successor, if the inorder successor has a right child, call the one child deletion algorithm

For example: if you want to delete the 3 node, replace it with the 4 node and then remove the 4 node for the example tree

Searching

Similarly to insertion, compare the node you want to find to each node, going down the subtree that matches your comparison

This is why the tree is called Binary Search– searching has an o(log n) time complexity