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.



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



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
Full course
Next Lesson