Making sense of the Binary Search Tree

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


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.


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.


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.



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