# A Guide to Binary Trees (Part 1)

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”

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.

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.

A proper Binary search tree

So let’s implement our tree!

First, we create our BinarySearchTree Class and initialize the root

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

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.

Written by

Written by