The Basics of Binary Search Trees

Photo by Todd Quackenbush on Unsplash

As I prepare myself for technical interviews, I have crossed paths with a common data structure known as a binary search tree. A binary search tree (BST) is simpler than what the name suggests. Let us breakdown what BSTs are and an example on how they can be used.

Definition

A BST is a data structure in which each node has at most two children. The value of each left node is less than its parent, while the value of each right node is greater than its parent. We can think of a BST like an upside-down tree. The root of the tree is the topmost node. The parent is the branch of the tree. This branch can have two other branches coming off them which are the child nodes. The two child nodes that are attached to the same parent node are siblings. These branches can have leaves. A leaf node has no children nodes and ends that section of the branch.

Basic Diagram of a BST

Following the above example, we see that our root node has a value of 22. The left child node has a value of 13, less than 22, and the right child node has a value of 30, more than 22. As we continue down the tree, all the child nodes on the left side must have a smaller value than their parent node, and all the child nodes on the right side of each node must have a bigger value than their parent node. As stated earlier, each node has at most two child nodes.

Searching Values in a BST

Let us say we want to search for a certain value in this Binary search tree above. We want to find the node with a value of 15. We can first ask is 15 greater than or less than 22? 15 is less than 22 so we know we will be on the left side. We ignore the right side of the root and move on to the left side.

Finding a node in a BST

We check if this node as the same value as our target node. No, 15 does not equal 13. We ask ourselves these same questions as we go. 15 is greater than 13, so we go right. Next row, we check again if 15 equals 18. We see that it does not, it is actually less than 18, so we go left. We check to see if the value of the node is 15 and it is! We can return that we have found the node.

Inserting Values in a BST

Inserting a node works very similarly to how searches work. We start by checking if our root has child nodes. We then compare the value we wish to insert to our root node, checking whether it’s bigger or smaller. Let’s say we want to add a node with a value of 23.

Inserting a node in a BST

We can follow the same steps. We see that our root has both of their child nodes. Our new node has a value of 23, greater than 15, so we will go down the right branch. The node with a value of 29 does not have any child nodes. We will insert our node to the left side since 23 is less than 29. We can follow this same pattern as the tree gets bigger.

Resources

For more resources on binary search trees, I suggest looking at these helpful links.

Really cool demo https://www.cs.usfca.edu/~galles/visualization/BST.html

https://medium.com/@ramyjzh/data-structures-for-dummies-binary-search-trees-13f87a1313a2

https://medium.com/swlh/understanding-data-structures-binary-search-trees-a6612daf00dd

https://www.geeksforgeeks.org/implementation-binary-search-tree-javascript/

Flatiron School software engineering alum. Experienced in JavaScript, React.js, Ruby, and Ruby on Rails. https://www.linkedin.com/in/chandler-hanson/

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