This Week in Coding: BST

As I continue my journey with algorithms and data structures I thought it would be a good idea to get a better understanding of binary search trees. But, what is a tree? A simple explanation is that it is a data structure that consists of multiple parent and child relationships, with a branching structure.

So what is the correct terminology to use when referring to a tree?

• Root- The top node in tree
• Child- A node that is directly connected to another node when moving away from the root
• Parent- The converse notion of a child
• Siblings- A group of nodes that have the same parent
• Leaf- A node that does not have any children
• Edge- The connection between nodes

There are a lot instances that we may utilize trees. A few are: HTML DOM, Abstract Syntax Tree and Artificial Intelligence.

How do binary search trees actually work? We start with the root node and every parent node has at most two children. Every node to the left of the parent will be less than the the parent node, with the right node always being greater than the parent node. Below I have implemented a the Node class and BST with insert.

We have the ability to insert a value into the tree, but let’s add a find method.

• First let’s check if there is a root. If not, return false.
• Set variable to track the current node.
• Set variable to track if we found the value.
• Set up a while loop that will loop through as long as there is a current and found is equal to false.
• Check to see if the value is less than current or if is greater than current. Set current accordingly.
• If value is found update found.
• If the value is found return current else return false.