BSTs

As a continuation of my last post, I am going to go more in depth with the different kinds of trees. Today I will talk about the first kind of tree that I learned about in school, and that’s a Binary Search Tree, or BST. A BST is a tree in which the maximum amount of children that a node can have is two. Also the nodes are set up so that the left subtree contains a smaller number than the root, but the root is smaller than its right child. A BST supports a lot of functions, such as search, sort, insert and delete.

The insert function puts a node at the bottom the tree, following the root down, and going to the left or right depending on if it's greater or less than the root, until it reaches a null node. The delete function deletes a given node, and then switches that position with the nodes successor. It is also fairly easy to search, by going left or right depending on the value until you reach a null node or the value you were looking for. My next post will be comparing the BST to a Heap tree so look for that coming up soon.