Example from the web app, here.

Why

A developer is hired by a small city of one hundred thousand. The task is to convert the city’s paperback phone book to a digital phone book. The mayor of the town has one requirement for the project: the digital 📖 phone book must be able to 🔍 find phone numbers at ⚡ lightning speeds.

Option A:

One logical approach for finding phone numbers would be to start at the beginning of the phone book. Then check if the page contains the desired phone number. If the page does not contain the desired phone number, flip the page over and try again. Continue flipping pages until the phone number is found.

This approach works, but also requires visiting all pages from the front of the book up to the desired phone number. In computer science, this would be comparable to placing the phone numbers in a linked list, and searching from the head of the list. Imagine if the desired phone number was placed in the middle of the city’s phone book. That means to find the desired number there would be fifty thousand page flips, and no one actually does that with a real or digital phone book.

Option B:

What one normally does is open the phone book somewhere near the middle and ask, “is the desired number smaller or larger than the phone number on this page?” If the desired number is smaller flip a handful of pages to the left. If the desired number is larger flip a handful of pages to right, and then check again. On each iteration the search becomes significantly narrower. In computer science, this technique would be comparable to placing the phone numbers in a binary tree and searching from the root of the tree.

When using a binary tree any desired number of the one hundred thousand phone numbers can be found in normally sixteen page flips. This is why a binary tree provides a manageable approach to finding values.

What

A binary tree is a collection of objects that are connected together through left and right pointers. Each connection, be it left or right, is based off of a binary comparison.

If there are no nodes in the tree, the incoming node becomes the root of the tree. In the example above the root is ten. Now notice the node to the left of the root, five. Five is less than ten. Go one level deeper. Notice the node to the right of the five, seven. Seven is greater than five, but seven also is less than ten. Seven was placed to the left of ten, and to the right of five. This binary placement creates a very specific subset. Let’s take a closer look at what exactly the binary tree is doing.

Say an engineer was looking for the value eight in the tree below.

The engineer’s code would first compare the desired value, eight, with the root value ten. Eight is smaller than ten, so the program would traverse to the left. In other words, the value eight is never going to be in the right sub tree. By knowing that the eight can never be in the right sub tree, the engineer is able to excluded half of the possibilities.

On the next iteration the eight will compare with the value five, but since eight is larger than five, this time the program traverses to the right. In other words, now the value of eight is never going to be in the left sub tree. After this second traversal, the engineer once again excludes another half of the tree. See below.

On the third iteration, the eight compares with the value seven. Since eight is larger than seven the algorithm again goes to the right, and once again another half of the remaining possibilities are excluded.

Now the eight is three levels deep on a leaf. The eight value compares with node’s value, eight, and equivalence is found. The algorithm has now arrived at the desired node.

Make a binary tree using the web app here.

How

Now lets build a binary tree 🌲, then we will test the tree and calculate how ⌛ long the code takes to find a value in a tree of one hundred thousand.

Let’s start with the node structure.

The node struct has an integer called val, this will store the phone number. Next the struct defines two pointers, left and right, for values smaller or larger than the node. Lastly a constructor is declared to pass values to the node. Notice the constructor also initializes the left and right pointers to null.

node structure:

struct node {
int val;
node* left;
node* right;
node(int v_) : val(v_), left(NULL), right(NULL) {};
};

Next let’s provide a layout for the BinaryTree class.

The private section of the class contains: a node struct, a node pointer root, and an overloaded print function.

The public section of the class contains: functions to add nodes, find nodes, print nodes, and a class constructor.

Notice the public print function does not take in parameters, unlike the private print function.

Source link