A Guide to Binary Trees (Part 1)

Eugene Grady
Feb 23, 2020 · 4 min read

There are many types of data structures within the world of programming. Most new coders are aware of structures such as arrays and hashes, but binary trees on the other-hand, especially for a bootcamp grad, are not as well known and/or understood. This series will explain what binary trees are, why they are used, and how to traverse them as well as showing some real world examples in their implementation.

In part 1 of this series, we will cover the following:

What is a Tree?

What are the differences between a tree and binary search tree?

How do we implement a binary search tree?

Now, what is a tree?

A tree is a data structure a data structure that consists of nodes in a parent-child relationship that can consist of any number of nodes. It is easier to think of an actual tree branching from one “root”

Image for post
Image for post

Photo by Mahkeo on Unsplash

A trees nodes can point to more than one node or no nodes at all! And just like a linked-list (another data structure I will cover in a future article) We can store data in each node. Another thing to remember is that trees are non-linear.

What is non-linear? It means data items are not organized sequentially. In other words, A data elements of the non linear data structure could be connected to more than one elements to reflect a special relationship among them. All the data elements in non linear data structure can not be traversed in single run.

Image for post
Image for post

An example of a Tree data structure

Now, what is the difference between a tree and a binary search tree?

So a binary search tree is different for several reasons. For one, the parent node cannot have more than two children. Also, the left child will always be < than the parent node, while the right child will always be > than the parent node.

Image for post
Image for post

A proper Binary search tree

So let’s implement our tree!

First, we create our BinarySearchTree Class and initialize the root

Image for post
Image for post

The root is initialized with a value of null

Next lets create our Node class and initialize it with values and the ability to have left and right children

Image for post
Image for post

Now let’s insert values into our Binary Search Tree. But first, let’s pseudocode our process.

Let’s create a new node. Then, starting at the root, let us check if there is a root, if not — the root now becomes that new node! If there is a root, check if the value of the new node is greater than or less than the value of the root.

  • if it is greater
  • check to see if there is a node to the right
  • if there is, move to that node and repeat these steps
  • if there is not, add that node as the right property
  • if it is less…repeat the above two steps

Now let’s write this out in Javascript

class Node {
constructor(val) {
this.val = val
this.left = null
this.right = null
}
}class BST {
constructor() {
this.root = null
}
insert(val) {
let newNode = new Node(val);
if (this.root === null) {
this.root = newNode;
return this;
} else {
let current = this.root;
while (true){
if (val < current.val) {
if (current.left == null){
current.left = newNode;
return this
} else { current = current.left}
} else if (val > current.val) {
if (current.right == null){
current.right = newNode;
return this;
} else {current = current.right}
}
}
}
}
}let tree = new BST()
tree.insert(5)
tree.insert(7)
tree.insert(3)
console.log(tree)

And we made our first tree! In Part 2 we will learn how to traverse through the tree using several different techniques. We will also discuss the Big O time of each technique and start to apply our knowledge to real world examples.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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