Linking the nodes

This is part two in a series of blog posts for my ‘IT Professional Skills’ module

In the last installment, I provided a quick primer on what a binary tree is and how to declare the necessary building blocks for creating one in C. I had declared a struct of type node that I can use to build my binary tree.

As a refresher, this is what my node looked like:

struct node
{
  char        *data;
  struct node *left;
  struct node *right;
};

The branches of my binary tree together are the left and right pointers. Each node has between zero and two children, pointed to by its left and right pointers.

Let’s imagine a use case for a binary tree. If I wanted to write a program to read in a text file and print each unique word to the screen in alphabetical order, I could do so using a regular array. However, since the text file could be abritrarily long, it’s inefficient and inconvenient to perform the sorting and linear searches necessary to make sure I don’t store any duplicates. To be exact, searching would probably be an O(n^2) operation.

Instead, I could keep my list of words sorted at all times in a tree. The first encountered word is the root, with all of its left-sided children being lexicographically smaller than it, and all of its right-sided children being lexicographically larger than it. Each child, in turn, shares this same property.

In this format, each new word can be traversed down the tree until it either hits its duplicate, or reaches an empty space–exactly where it should be.

For example, consider the following sequenced input from a text file:

even now bark adjust council tigers yield

The binary tree produced from the program I’ve described above would look like this:

Here, the data in the root of the tree is the word “even”. The next word in the sequence is “now”, which is lexicographically greater than “even”, which results in it becoming a right-sided child of the root. The next word “bark” is lexicographically smaller than the root, so it’s sorted as its left-sided child.

Consider, as a small exercise, the path of the word “council”. While it’s lexicographically less than “even”, it’s greater than “bark”. Can you trace its path?

Stay tuned for the next installment, where the program itself will begin to take shape.