Binary Search Trees

What is a binary search tree?

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

‍

Examples: 

Draw out the following tree: 

1. Insert 5
2. Insert 2
3. Insert 4
4. Insert 8
5. Delete 4
6. Insert 3
7. Insert 1
8. Insert 7
9. Insert 9
10. Delete 5