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:

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

The tree is generally represented in a top-down configuration like in this image. The top node is the root, and each of the nodes that sprout from the root are its children. This is also true for each of the children, each child is a node, and therefore can have children of its own.

Any node (apart from the root) that has children is known as an internal node (also called and inode or branch node), and an external node (can also be called a terminal node or leaf node) has no children. An edge (or link) connects nodes together. The height of a node is the length of the longest path between that node and an external node. The depth of a node if the length of the path between the node and its root.

Binary Search Tree

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

A Binary Tree is a tree data structure where each node has at most two children, which are referred to as the left child, and the right child. Also, whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

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.

Writing this has really help solidify this conceptually for me. That being said, I’m still going to need a lot of practice before I can write one of these functions off the top of my head. Hopefully this will serve as a good starting point for my junior dev peers.