Topics About Contact Resources Quotes

Interactive Binary Tree

A binary tree is a simple data structure.
A data structure does what it sounds like, it structures data, that is, it makes data easier to work with.

We have a large collection of books, how can we use a binary tree to store them?
We need to use a property of our books as a key so our binary tree can structure our books.
We could choose the book's publish date, the number of copies sold, the price, etc,
but we'll choose the book's page count as our key.

Storing our books in a binary tree allows us to add/find/remove books in a logical way based on our key.

How Does It Work

Let's continue with our book data set.

Each of our books will be nodes in our binary tree.
Each node can have 2 children a left and right child node.

Inserting our first book, it becomes our root node.

When we insert another node, we have 2 choices of where to put it, to the left or to the right of our root.
We decide where it goes based on our key

So, we need a way to compare 2 nodes based on their key values.
We'll put our new node to the left if it has less or the same number of pages than our root node, and we'll put it to the right if it has more pages than our root node.

Then, with each new node we repeat that process, with one more step, we check if our desired position is already occupied.
If not, then we're done,
if so, then we descend the tree by repeating our key value comparison on any node that is occupying our desired position, until we find an empty position.

So, we have a logical way of navigating our tree.

Note that we could've switched which books go left vs right, as long as we're consistent.

What Are the Advantages of Binary Trees

Binary trees could give us performance advantages in certain situations.

For example, if we stored our books in an array, we would have to check each book to find which had the most/least pages, a binary tree allows us to avoid many checks.

If we need to interact with our data based on a key, a binary tree could be a good option for us.

Where Does the Name Come From

The word binary comes up a lot in the tech world, for example a binary search, binary simply means 2 choices.

What about the tree, well as we can see, when our binary tree is drawn it often resembles a tree...

Resources