Binary Tree Implementation in C#

Today we will explain the groundwork for building the some basic binary tree functions. If you are familiar with nearly any programming language you have most likely used data structures to hold multiple pieces of information.

Common data structures/containers include:

  • Arrays
  • Vectors
  • Stacks
  • Queues
  • Linked Lists
  • Maps
  • Trees
  • and more!

The most commonly used tree is the binary tree. So we will focus on this one for now. To begin, why would we want to use a binary tree in the first place?

The two main reasons for using a binary tree are:

  1. To help visualize the data in a hierarchical fashion. (File systems use this, along with HTML DOM)
  2. Speed up the time taken to find/modify an element within the set.

What does it mean for data to be stored hierarchically? Lets start of with an image to help convey the idea!

 Think of these integers the same way you would if you were storing them in an array. With an array you can add data in sequential adjacent memory locations. If you want the array to have an ordered set of numbers you can either add these numbers when the array is initialized or dynamically add them at run-time. What about the scenario where your array is full and you need to add additional items to your list? This would require you to allocate new memory for another array and then set a larger index for that array. With a binary tree, your data will always be in order and adding new numbers is as simple as passing your data into an insert function.

This image shows the hierarchy (ordering by rank) of a list of integers. Each of these circles we will call a node, with each node containing a value that can point to a maximum of two other nodes. The top node (8) is called the root node. You will always begin your search of a value from the root node.

You can think of this as the root of a tree, with connected values branching downward. From the very top root node, there are two connected values (using pointers) with the left value 3 being LESS THAN 8 and the right value 10 being GREATER THAN 8. If you need to find or manipulate any of the numbers in this list, you could do this using an algorithmic process explained below.

  1. Look inside the root node.
  2. If the value you are looking for is greater than the root node, go right.
  3. Otherwise if the value is less than the root node, go left.
  4. Repeat the process until the number you are looking for is found!

This not only helps us visualize how the data is being traversed, but also will allow us to find a value without having to potentially look at every single element/memory location to find it. In the worst case scenario of searching through an array, the number you are looking for could always be saved at the very last element of the array. This can give us very bad performance if we are traversing hundreds of millions of numbers!

In fact, if we have a number of elements the complexity approaches big O(N) (N being number of elements being looked at), while a Binary Tree helps to reduce the number of potentially searched elements to a complexity of O(log(N)) during the worst case scenario.

Let us take a look at the actual implementation of this binary tree:

This tutorial is designed using Visual Studio. You may download a free copy of Visual Studio 2017 if you haven’t done so already. You can find a tutorial on how to setup a C# project listed within our tutorials page.

  1. Start a new C# project in Visual studio at the top left hand corner using File > New > Project.
  2. Under templates, select Visual C# and then choose Console App (.NET Framework)
  3. Name the project with anything suitable. In this case I will call our project BinaryTreeTut

You will then see the standard C# libraries included inside of every C# project. For now we wont be needing most of these libraries, except for System, System.Text, and System.Collections.Generic

using System;
using System.Text;
using System.Collections.Generic;

Next we will need to create a new class to implement the Binary Tree structures. We can do this by going to the Solution Explorer on the right-hand side of the screen.

  1. Right click on the BinaryTreeTut in the solution explorer.
  2. Scroll down to Add and then select New Item.
  3. Then select Class and we will name this class BTree.cs

Great, now we have a class where we can start building functionality of the Binary Tree. Once again you will only need the System and System.Text libraries. I will now list the steps needed for each piece of our tree and explain each part.

  1. Within the BinaryTreeTut namespace, we will define a class to store our constant variables (ones that will not change throughout the duration of our program). This will be used when we generate a random series of numbers to insert into our tree.
  2. Inside of this class we will declare the a public variable called MAX_SIZE. This is the maximum number of nodes (or elements) that will be contained inside of our Binary Tree.
1
2
3
4
5
6
7
8
9
10
11
12
namespace BinaryTreeTut
{
    static class Constants
    {
        public const int MAX_SIZE = 10;
    }
 
    class BTree
    {
 
    }
}

Now we will define another class called Node below the Constants class and above the BTree class. I would like to familiarize you with some binary tree terminology that will be used.

  1.  Each value inserted into the tree is considered a node. The image to the left has a total of 9 nodes. Newer nodes are added below existing nodes.
  2.  The initial value first entered into the tree is referred to as the root node. It it possible for the root node value to change  if you have a self balancing binary tree.
  3.  When the current node points to another node below, it is referred to as the parent.
  4.  When the current node is a branch located below another node, it is called the child.
  5.  Each pointer in the binary tree can be called an edge.
  6.  Any node which does not have any children below it is called a leaf.
  7. No two nodes should contain the same value.
  8. When searching or inserting into a binary tree, you will always start at the root node.
  1. Each node in the binary tree will hold three items. They include:
      • An integer called value, which is used to hold the next number to be inserted into the tree
      • A node object called left, which will hold any value that will be inserted to the left of the previous node. Nodes to the left are generally smaller numbers than their parent node.
      • A node object called right, which will hold any value that will be inserted to the right of our previous node. Nodes to the right are generally larger numbers than their parent node.
      • These node objects are actually pointers that point to the address of the of the nodes below.
  2. We then define a constructor for our Node class. This will be a default constructor that will initialize the three variables listed above to default values.
  3. Finally we can add a parameterized constructor which will allow you to specify the value you wish to insert within the node. The code for this is shown below
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Node
{
    public int value;
    public Node left = null;
    public Node right = null;
 
    public Node()
    {
        value = 0;
        left = null;
        right = null;
    }
 
    public Node(int newItem)
    {
        value = newItem;
        left = null;
        right = null;
    }
}

In order for our BTree class to use the Node class we must define a node to be used as our root and a node to designate the current node we are using. We must also add a counter that will be used when we display all the values in the binary tree.

public class BTree : Node
{
    public Node root = null;
    public Node currentNode = null;
    static int mcount = 0;
}

Now we can start working on the creating the functions needed for a binary tree to operate. Start with the insert function, which is the most essential routine used for building your tree. Here is a description of what is happening within this function.

  1. We will define the function with a parameter called item. This will be the current value we wish to insert into the tree. Right now we are just using simple integers, but a binary tree can be expanded to include virtually any data type you can think of.
  2. Next we will check to see if a root node current exists. If the root node is null, this means our tree is currently empty and will need to make this first piece of data the starting point of the tree. We do his by allocating a new Node object (with the item passed in) and pointing our root pointer to this node. This root node would also be assigned to the current node we are working with.
  3. Otherwise if a root node is found, we will have to use a decision making process to decide where to place the next data element.
  4.  Let use start off by initializing another node called the parent node. Once the current node we are working with has children added to it, it will be considered a parent node.
  5.  Now comes the core conditional statements that our binary tree will use to decide where to put our item.
    • Start by checking if the item to be inserted is less than our current node’s value.
    • If it is less, then we must check and see if the left child node has any data in it.
    • If there is no data within the child left child node, we can go ahead and initialize a new node to the left and set that nodes value to our current item value.
    • If there data exists in the left child node, then set the current node to the parent node and the next left child node as the current node to be traverse.
    • We can then recursively call the insert function once again, with our new parent and current nodes. This is the equivalent of traveling down the left hand paths of the binary tree.
    • Now if the item to be inserted is greater than our current node’s value, we are going to traverse down the right sided nodes.
    • Repeat the process used for traversing down the left sided nodes, except using the right sided nodes this time.
    • Finally when we are done, reset the current node back to the root node so that we can start our traversal from the root node once again.

Here is the final version of insert() below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public void insert(int item)
{
    if (root == null)
    {
        root = new Node(item);
        currentNode = root;
    }
    else
    {
        Node parentNode = new Node();
        if (item < currentNode.value) 
        { 
            if (currentNode.left == null)
            { 
                currentNode.left = new Node(); 
                currentNode.left.value = item; 
            } 
            else 
            { 
                parentNode = currentNode; 
                currentNode = currentNode.left;
                insert(item);
            }
        }
        else if (item > currentNode.value)
        {
            if (currentNode.right == null)
            {
                currentNode.right = new Node();
                currentNode.right.value = item;
            }
            else
            {
                parentNode = currentNode;
                currentNode = currentNode.right;
                insert(item);
            }
        }
        currentNode = root;
    }
}

When it comes time to build our binary tree, we will be using this function quite a bit. Once the binary tree is built, we will need a way to display each value in the tree. The a function named display will be used for this purpose. Here is a quick explanation of how display works.

  1. The parameter value i will be the current nodes value. The display function must be called for each item that you want to display. The function contains a static counter called mcount, which will allow you to display up to MAX_SIZE items.
  2. The items in the binary tree will be separated by spaces.
public void display(int i)
{
    if (mcount < Constants.MAX_SIZE)
    {
        Console.Write(i);
        Console.Write(" ");
        mcount++;
    }
 
    if(mcount == Constants.MAX_SIZE)
    {
        mcount = 0;
    }
}

Now that we have a simple function to display each item in the binary tree, we will also create three traversal methods that will specify which direction down the binary tree to take. Here is an explanation of how each traversal method works.

  1. inorder: Check if the left child has data within it. If it does not, go into the left branch and call inorder again. If there is no left child value, then display our current value. Once the value has been displayed, check if the right child has any data. If it does, go into the right branch and recursively call inorder. You can think of this method as check left branch, display value, then check right branch.
  2. postorder: Check if the left child has data inside. If it does then go inside the left child and recursively call preorder. If no data exists in the left branch, then check the right child and see if data is inside. If we have data here, go inside the right child and make a recursive called to preorder. Finally if both left and right children are null (do not contain any data) then display the current value. Think of this method as check left branch, check right branch, then display the value.
  3. preorder: Display the current value. Then check if the left child has data inside, if so go into the left branch. If no data is inside, then check if the right branch contains anything. If the branch branch contains a value, then go into the right branch. Think of this method as display value, check left branch, check right branch.

*Note: You are passing an the actual reference to a Node objects location in memory, not a copy of the object. An Action is a delegate in C# that can be thought of as a function pointer. It will allow you to pass the display function into Action f. This is useful when you decide to use comparators to display the values in descending or ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public void inorder(ref Node node, Action f)
{
    if(node != null)
    {
        if (node.left != null)
        {
            inorder(ref node.left, f);
        }
 
        f(node.value);
 
        if (node.right != null)
        {
            inorder(ref node.right, f);
        }
    }
}
 
public void preorder(ref Node node, Action f)
{
    if (node != null)
    {
        f(node.value);
 
        if (node.left != null)
        {
            preorder(ref node.left, f);
        }
 
        if (node.right != null)
        {
            preorder(ref node.right, f);
        }
    }
}
 
public void postorder(ref Node node, Action f)
{
    if (node != null)
    {
        if (node.left != null)
        {
            postorder(ref node.left, f);
        }
 
        if (node.right != null)
        {
            postorder(ref node.right, f);
        }
 
        f(node.value);
    }
}

Currently we have enough functionality for the binary tree to actually start building one. Let us head back to the main namespace BinaryTreeTut namespace located within Program.cs (this may vary depending on whether you changed the main program name or not)

Here is a description of the program that creates and displays a binary tree.

  1. Begin by creating a Random object call rand. Random is just a class provided by c# for generating ranges of pseudo-random numbers.
  2. Then we create a BTree object using the class we created throughout this tutorial.
  3. We will also define an array of integers which will hold our randomly generated numbers.
  4. Loop through the size of your number list. Generate a random number between 1-10 and store this in nextRand.
  5. Check if our list currently has this number, if not store the randomly generated number. Otherwise skip this number and lower our counter. This ensures that we will generate all numbers between 1 and 10 inclusive. The list will be ordered in a random arrangement.
  6. Once we have our randomly ordered values in our array, we can loop through the array using foreach and insert each of these values. After all the values are inserted our binary tree has been generated!
  7.  You can examine the effects of each traversal method. As a side note, remember the inorder/postorder/preorder functions have the root node passed in, along with the display function. Each traversal will always start with the root node, but may change direction depending on the values of the children below.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static void Main(string[] args)
{
    Random rand = new Random();
    BTree tree = new BTree() ;
    int[] values = new int[Constants.MAX_SIZE];
 
    for (int i = 0; i < Constants.MAX_SIZE; i++)
    {
        var nextRand = 0;
        nextRand = rand.Next(1,11);
        if(!(values.Contains(nextRand)))
        {
            values[i] = nextRand;
        }
        else
        {
            --i;
        }
    }
 
    foreach (int value in values)
    {
        tree.insert(value);
    }
 
    Console.Write("Inorder traversal: ");
    tree.inorder(ref tree.root, tree.display);
    Console.Write("\n");
 
    Console.Write("Preorder traversal: ");
    tree.preorder(ref tree.root, tree.display);
    Console.Write("\n");
 
    Console.Write("Postorder traversal: ");
    tree.postorder(ref tree.root, tree.display);
    Console.Write("\n");
 
    Console.Read();
}

Feel free to download the solution for this example provided below!

Posted in Programming.