Using binary search tree with traversal logic injected from the outside. Datastructures should not depend on any hardcoded logic. It is important because otherwise moving the structures from a console application to a WPF application would be impossible. Depentency injection is an important terminology in programming.

Problem

I’ve already created a post about binary search tree together with a YouTube video, so if you want you can check them out here. There is one important thing that should be kept in mind: datastructure only used to store data and nothing else. It is quite simple until we face the problem of traversal. When we need to process the full structure at first we always use some basic writing method eg. Console.WriteLine() or console.log() or System.out.println() or many other options, based on which language are we using. The problem occurs when we hardcode these method calls inside the datastructure!

Solution

In order to solve this problem, we have to use delegates which are basically method references. Inside a delegate you can store references to methods. You can imagine it like having an array with methods inside, instead of integers. It’s important to note that all method must have the same signature (return type, number of parameters, types of parameters, order of parameters).

Coding

BSTree class

Creating the base class

At first we create the binary search tree class, with generic T and K types and with nested tree item class inside. Additional methods like insertion are not mentioned here, but you can check the full code here if you want.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class BSTree<T,K> where K : IComparable
{
    private TreeItem root;
    class TreeItem
    {
        public T content;
        public K key;
        public TreeItem left;
        public TreeItem right;
        public TreeItem(T content, K key)
        {
            this.key = key;
            this.content = content;
        }
    }
    // ADDITIONAL METHODS...
}

Adding the delegate

Then we add the delegate, which will be our key point here. With this delegate I state, that only methods can be stored inside thsi delegate which have void return type and which have one parameter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class BSTree<T,K> where K : IComparable
{
    public delegate void TraversalHandler(T content);

    private TreeItem root;
    class TreeItem
    {
        public T content;
        public K key;
        public TreeItem left;
        public TreeItem right;
        public TreeItem(T content, K key)
        {
            this.key = key;
            this.content = content;
        }
    }
    // ADDITIONAL METHODS...
}

Next step will be to create the traversal method which in this example will be a simple PreOrder traversal. (In the full code you can see PostOrder and InOrder as well.) From the Traverse method I call the PreOrder private method. This separation (public / private) is a must, otherwise you wouldn’t be able to call with the root parameter and then call is recursively. (Think about it.)

And as we can see, I put the method which needs to be run as a parameter to the Traverse method, which then passes it forward to PreOrder method. Inside this I call it after checking that it is not empty. We could also use methodToRun?.Invoke(p.content) form as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void Traverse(TraversalHandler methodToRun)
{
    PreOrder(this.root, methodToRun);
}

private void PreOrder(TreeItem p, TraversalHandler methodToRun)
{
    if(p != null)
    {
        if (methodToRun != null) methodToRun(p.content);
        PreOrder(p.left, methodToRun);
        PreOrder(p.right, methodToRun);
    }
}

Adding the logic

By the logic I mean “how to process a given node”. Our goal was to remove the internal hardcoded Console.WriteLine call, and be a bit more flexible. Above the Main() function, we create these two methods. Inside the Main() function we create the object, insert a few dummy inside and start the traversal. Note that I used Person type everywhere, which means that I have not violate the T type usage. This is a self-made simple class.

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
class Program
{
    static void ProcessingMethod(Person p)
    {
        Console.WriteLine("\t==>\t" + p);
    }

    static void ProcessNodeToFile(Person p)
    {
        StreamWriter sw = new StreamWriter("MY_OUTPUT_FILE.txt", append: true);
        sw.WriteLine(p.ToString());
        sw.Close();
    }

    static void Main(string[] args)
    {
        BSTree<Person, int> bst = new BST<Person, int>();

        bst.Insert(new Person(){ Name = "Linus Torvalds" }, 10);
        bst.Insert(new Person() { Name = "Steve Jobs" }, 20);
        bst.Insert(new Person() { Name = "Bill Gates" }, 1);

         // will output to the console
         bst.Traverse(TraversalTypes.PreOrder, ProcessingMethod);
         
         // will output to the file
         bst.Traverse(TraversalTypes.PreOrder, ProcessNodeToFile);
    }
}

Result

As a result, we now have a datastructure (currently a BST but it can be a linked list or whatever we need) which is able to use any external logic to process the nodes. With this trick, we have a more versatile structure to use. The inner logic part can be swapped to whatever we need, eg. sending the node’s content to an API endpoint which then logs the data to a database.

Downloadables

You can download the full solution by clicking here.

Or use CLI with these commands and then look for the BINARY SEARCH TREE folder:

1
2
cd Desktop && mkdir Downloaded_Project && cd Downloaded_Project
git clone https://github.com/data-structures.git