Today I will explain a data structure that is efficient for searching and sorting. You may have already guessed it, it’s the Binary Search Tree (BST). This blog will be based upon the assumption that the reader is already familiar with binary trees. Let’s begin.

Binary search trees are a subset of binary trees. They are basically binary trees with some extra restriction. This BST property is that every node, n, has a rule that: all nodes in the left subtree have smaller values than n, as well as, all nodes in the right subtree have larger values than n.

Here is an example of a Binary Search Tree.

You may be wondering now, how does this make searching efficient in a BST? We come to the observation that: if we are searching for a number, x, when we compare x to the root node and if x is not equal to the root, then we can eliminate one of the subtrees to search in. More precisely, if x is smaller than the root, then we search the left subtree, as it contains all the numbers smaller than the root node. Likewise, if x is larger than the root node, then we search the right subtree. If we run out of nodes to search, then x is non existent in the tree. This is the algorithm used to search a BST.

Comparing BST search to a linear search, we can further analyze the efficiency of this data structure. When searching in a linear list or a binary tree, the worst case is that we will have to make comparisons equal to the total number of nodes. When searching in a BST, the worst case is dependent on the height of the tree.

However, there are many ways of composing a BST, each with different heights. Here is an image displaying a bad BST, on the left, vs a good BST, on the right.

Hence, it’s important to minimize the height of the tree. A complete binary tree, also known as a balanced tree, with n nodes is a binary tree such that every level is full, with the exception of the bottom level which should be filled in left to right. A complete binary tree has the minimum height of any binary tree with n nodes. This minimum height, h, satisfies the following expression:  h ≤ log₂ n. Which can be proven simply by using induction.

Therefore, if the binary search tree is also a complete binary tree, searching the BST can take log(n) steps, which is much faster than linear time.

There are many ways to represent a BST, and I challenge you to build the necessary classes and methods needed. It may come in handy one day. I hope you learned a thing or two about the binary search tree data structure, and until next time, peace. ✌

Have you ever had a professor that was so good, they made you love the subject? My organic chemistry professor this semester, Dr. Andrew Dicks, has made me love chemistry even more. His confidence, teaching style and understanding of the concepts make him an amazing speaker. I believe that, to some extent, loving a course and its contents is related to the professor and their way of teaching. When the lecturer is excited about what they are going to teach, it reflects on to their students.

The first lecture I attended for organic chemistry 2 was one of my favourite lectures. It was a review on the concepts I had learnt in a previous course. Instead of being bored, since I already knew the concepts, I found myself beginning to understand the concepts that I thought I knew well. It occurred to me that I had just known or memorized some of the concepts before. The professor focused on trying to get the students to understand the main idea, and from there everything can be solved.

The lecture was very interactive, with in-class problems to work on and take up. Then, relating the concepts to the real world. The professor knew how to break up a big and difficult concept to students who knew no such thing about it. Beginning with very simple explanation and building on. I truly enjoyed his teaching style, with minimal slides and adding on some additional details in lecture.

I look forward to every lecture in this class, even though it is a very tough course. Just when I thought chemistry couldn’t get better, Dr. Andy Dicks has inspired me to take more courses related to organic chemistry.  I hope that all of you encounter an amazing professor in your life that will make you love a subject even more.

Until next time, peace. ✌️

It was just two weeks ago that I attended a hackathon. I was eager to get there, and start on my hack. However, it did not really go as planned. Here is the story of my failure, or maybe just my best project yet.

I know myself, I’m not a very experienced programmer. The projects I have worked on have always been course assignments, and we were always given starter code for them. This time, I had to write the starter code myself. I had to figure out what to do. So, I decided to choose an idea that wasn’t so hard to learn and achieve. I had the idea of creating a chrome web extension that will ultimately change the layout of the page you are browsing. Creating a web extension couldn’t be so hard, or so I thought.

I worked with a partner, who was a very close friend that I met first year at UTM.  We started out by watching YouTube tutorials, and reading instructions on how to create a web extension. Once I created the required files for my extension and added the set-up code, I was left with trying to figure out how to implement my idea into code. I knew that I had to somehow read the website’s source code, then parse it to gather the necessary information that I need. I was stuck at this stage for almost a whole day. I was able get my web extension to highlight certain parts of the page in a chosen color. That was about it. I couldn’t figure out how to gather the other information I needed, or even how to put the information I gathered into action.

At this point, me and my partner were stuck, and we agreed that this level of programming was above us. So, we decided to change our plan of action, and take on a smaller task. We ended up building a web extension that stores your preferred sites. So, when I am using google chrome, I can click on my extension and I can get quick access to my preferred sites. I know what you may be thinking; well isn’t that just like bookmarks? Yeah, but, I designed it and I programmed it. It was something I had no idea how to do just yesterday.  

Building this “bookmarks” extension, got me a step closer to implementing the project I was set to do. It wasn’t a waste of time, or energy. Sometimes, we have to take a step back and look at the bigger picture. I could have stayed stuck at my position, or I could have taken a step back and slowed down a bit. We always want things to be done right away, but we need patience, and we need to make realistic approaches. This project, meant so much to me. It showed me how much I can learn in just several hours. This project pushed me to learn more about chrome extensions, so I can build my skills and develop my main idea.

I would sum up my experience in this phrase:

Always aim high, but don’t fear of slowing down.

And who knows, maybe my next blog post will be about my final chrome extension. Until next time, peace. ✌