Making sense of the Binary Search Tree

I grew up adjacent to software engineering, but never really full immersed in it. I learned HTML and CSS in middle school, I learned how to use the command line in highschool, and I thought myself how to program microcontrollers in college. I would call myself software savvy, but certainly no expert. That’s why I’m having such a hard time learning data structures. Being a self-taught programmer for most of my life, I had no foundational education in some of the more abstract parts of coding, particularly things like trees. In an effort to understand it more deeply, here’s my attempt at an explainer…

What is a tree?

First we should define what a tree data structure is. This definition is taken from wikipedia:

Binary Search Tree

Okay now that the basic terminology has been established, let’s look at Binary Search Trees (BST) specifically:

Binary Search Trees support three main operations: Search, Insertion, and Deletion

Searching

A search function can be performed recursively as shown in this example. The first if statement is the base condition: if the requested node doesn’t exist, or if it matches the search criteria it will return it. The first else if will move to the left if the search data parameter is less than node’s data and run the function all over again. The second else if does the same but moves to the right.

Insertion

In this example, the variable newNode is a new Node class. We start by providing the root node, and the new node. If the value of the new node is less than the root value, we move it to the left. If the left child is null we’ll insert the new node here. Otherwise we’ll run the function again, until the base condition is met. If the newNode data is more than the root value, we’ll run the same loop on the right side.

Deletion

We’ll use the same recursion scheme to start. The base condition will determine if the node exists, if not return null. If it does exists, first we’ll check if the data we want to delete is less than that of the current node, if we’ll run the function again on the left side. If the data is higher, we’ll run it on the right side. The last condition will run if the current node matches the delete parameter. If the found node has no children, set it equal to null and return the node. If there are children, set the current node to the child value, and return the updated node.

I take things apart, and then I put them back together again

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store