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. Although now there is an ordering to the values!

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.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
 
namespace BinaryTree
{
    static class Constants
    {
        public const int TREE_SIZE = 10;
    }
 
    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;
        }
    }
 
    public class BTree : Node
    {
        public Node root = null;
        public Node currentNode = null;
        static int mcount = 0;
 
        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;
            }
        }
 
        public void display(int i)
        {
            if (mcount < Constants.TREE_SIZE)
            {
                Console.Write(i);
                Console.Write(" ");
                mcount++;
            }
 
            if(mcount == Constants.TREE_SIZE)
            {
                mcount = 0;
            }
        }
 
        public void inorder(ref Node node, Action<int> 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<int> 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<int> 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);
            }
        }
    }
}