Week 9: Binary Search Trees

Here we are, back again, me writing, you reading about programming. What's this week you ask, binary search trees of course. "What's a binary search tree?" you may ask, well let me tell you. I binary search tree is like an ordinary binary tree, only the nodes are ordered or sorted based on certain properties. The left subtree will contain nodes with the root less than the trees root. The right subtree will contain nodes with the root greater than the trees root. Both the left and right subtrees are binary search trees as well as there are no duplicate nodes.


That's what defines a binary search tree by definition, let's look at an example of one. The image to the left is an example of a binary search tree. Notice the entire trees root is an 8. This means everything to the left of it must be less than 8. If we look at the left subtree, the root it 3, which is less than 8. Then we can look at that 3 as being the root of a binary search tree. Everything to the left of the 3 is less than it, being only the 1. Everything to the right of the 3 must be greater than it. 6 is the next root under 3. Everything to left of 6 must be less, which it is and everything to the right must be greater, which it is.

My experience with Binary search trees has contained some trouble itself. While I understand the concept of them and am comfortable with manipulating them. I find I have trouble with writing one recursively. But once again, this goes back to my trouble with recursion itself. I'm slowly improving, but I still find trouble dealing with subjects like this.