So my friend and I get together ofter to do some coding practice, algorithms or little mini projects. Lately when we meet up through zoom, we have mainly been doing algorithm or data structure work. Recently I had a take home coding challenge and to prepare for it the application had tree structures in the list for studying. Not being a Computer Science major, I have very little practice with trees, graphs, etc. I do know what they are, I know what a node is, and I have played with linked lists which are, to my knowledge, the most basic of node data structures.
My friend, while not having a full CS degree, had an AA (I think?) in CS or maybe he had studied these things on his own more extensively, I cant quite remember. But the point is, he thought it would be good practice for myself, and him to mainly refresh, by going over the Binary Search Tree data structure.
A binary search tree is a tree structure that follows a certain set of rules. It is a powerful way to organize data and can be navigated very quickly. Firstly, to understand the rules of a binary search tree the basic structure of a tree is necessary. A tree is essentially a collection of nodes. Nodes are, for lack of a better word, things that have a value or property and, in the case of a tree, a left and a right. The left and right are like arrows to the next nodes. This picture might give you a better idea of what a tree looks like.
The rules of a binary search tree are as follows. The nodes to the left of the root node are lesser than the nodes previous. The nodes to the right are greater than the nodes previous. Also the nodes to the left and the right are also binary search trees. If we look at the picture it is pretty clear what that means. The nodes in the left subtrees are lesser and lesser. The nodes to the right get higher and higher in value.
Now that we know how the binary search tree is set up we should be able to traverse it. There are some basic operations that are used with binary search trees often. We will want to be able to search for nodes, and insert nodes. In order to do these things we obviously have to navigate through the tree. The implementation of a binary search is actually quite simple. It can be done iteratively using a while loop or recursively.
Setting up our function iteratively we probably would have a couple parameters, a root node and a target node. Our while loop would be based on the condition that our root node is not our target node. I would make a variable that would first reference the root node as a placeholder. Then we can change the placeholder as necessary and move through the nodes until we found our target, if it existed in the tree. The way we move is by checking whether the left node is of a larger value that our target, if it is than we move left, if it is lesser than we move right.
Recursively, we would need again our root node and a target node. Then we would have 2 checks before our recursive case. We would check first that the node doesn't exist, and then if the node is our target value. If these two dont get hit, then we move into our recursive case of moving through the nodes, left if the target is lesser than our current node, right if it is greater. I wrote this as a class method at the time, so ignore the this.
The insert function works a bit similarly but we just have to make sure we place our node in the right spot. In order to do this we have to move through our nodes and then make sure where we put our node obeys the rule of the binary search tree. This bit of code I wrote is maybe not the prettiest way to get the insert done, but it works.
Top comments (0)