Data Structures (Part I) - Basic Binary Tree

A few months ago I went to a session on Generics in C# and came back decided to give them a try myself. To practice this new .NET feature I decided to use typical Data Structures like binary trees and B+ trees.

Data Structures have always been one of my favorite topics. When I was in college I got to write C/C++ programs to handle binary trees, n-ary trees, graphs, and such. Now with generics in C# I thought it would be a good excercise to write a generic binary tree and then a generic B+ tree. Even more, my exercises back then were limited to store the data and walk through the trees in order, but I never draw the trees on the screen. 

It's been a while since I wrote a program to represent binary trees, since the early 90s to be exact. So this time I started with the simplest example: a binary tree to order integers. That was simple, a couple of hours at a coffe shop and I had the program to store the numbers and walk through the tree in order. Then I decided to write a program to display on the screen how the tree was organized internally. Little did I know that this was much more complicated than I thought, but also a lot of fun. 

This post is the first in a series of programs to implement some common data structures in C#. I am planning on posting programs on binary trees and B+ trees. My idea is to post programs to handle integers (i.e. solve the problem first) and then update them to use Generics so that they can support any sortable data type.

Data Structures
Data Structures are structures used in computer science to organize information. For example, a binary tree or a linked list can be used to sort information as it is created. Some of these structures are the base for some of the technologies that we use on a daily basis. For example, databases (like SQL Server or Oracle) rely on algorithms similar to the B+ tree to create database indexes. 

The point of the examples that I am going to present is to ilustrate some of these data structures and a sample implementation in C#. If you need to use any of these data structures in a production environment I suggest that you buy a commercial libraries meant to be used under heavy loads. 

Binary Tree
Binary tree is a very simple data structure used to organize information. The following picture shows a binary tree storing integers from 1 through 7.

<p><img src="./images/nodes1_7.png"/></p>

In this example the root node is 4. All the numbers less than or equal to 4 are to the left of the root node. All numbers greater than 4 are to the right of the root node. The root node is the first node created for the tree. 

Below is another example of a binary tree. This one has 34 nodes with random numbers. The root node in this case is 363. From looking at the picture we can deduct that number 234 came after 368 and was stored to the left since 234 <= 363. We can also deduct that number 326 came after 234 since it's to its right (326 > 234)

<p><img src="./images/nodes34.png"/></p>

There are several books that have comprehensive information and theory about binary trees. If you are not familiar with the theory I highly recommend you take a look at some of the existing literature.

As I mentiond before, implementing a binary tree is relatively simple. You basically need a class to store node informaton and a class to organize the nodes. A node contains tree pieces of information: a value (in this case an integer like 363), a pointer to a node with a value less than or equal to the node's value, and a pointer to a node with a value greater than the node's value. 

To display the values of the binary tree in order we start at the root node. We then go to the pointer of values less than or equal to the root. We do this recursively until there are no more values on the left side of the nodes. Then we come up one level and start the same process to the right.

In the previous example the process will start on 363, go the left (234), go to the left (170), go to the left (34), go to the left (8) and print "8". Then, since there are no more values to the left we go up one level and print "34". Go to the right (98), go to the left (57) and print "57" since there are no mode nodes to the left. Go up one level, print "98", go to the right and print "158". So far the process would have printed: 8, 34, 57, 98, 158. If we keep going this way we will eventually print the 34 numbers of the tree in order. The following picture shows the order in which the nodes would be printed (see the numbers in red)

<p><img src="./images/nodes34withsequence.png"/></p>













A binary tree is composed of binary nodes. A binary nodes contains a value (e.g. the integer value), a pointer to a node less than or equal to the value, and a pointer to a value greater than the value.













