C# - Generic Class To Create Node Tree From Array
Tags: csharp
Published: 2020-08-07 00:19:54

Currently I find myself in the middle of a bunch of interview prep and am constantly running tests for Node Trees.

###The Problem###

If I test Breadth First Search (BFS), or Depth First Search (DFS), or reversing a Binary Search Tree (BST) I generally make a BST one line at a time...

```csharp
IntNode root = new IntNode(1);
root.left = new IntNode(2);
root.right = new IntNode(3);
root.right.right = new IntNode(5);
root.right.left = new IntNode(4);
```

This method is painful and, seemingly, takes forever.
Especially when I just want to test a single algorithm.
Don't even get me started on doing multiple tests...

###The Solution(?)###

I wrote a neat little helper class to automate this process!

```csharp
public abstract class Node<T, V> where T: struct where V: Node<T, V> { // in C# 8.0 you can use 'where T: notnull'
    public T val;
    public Node<T, V> left;
    public Node<T, V> right;

    protected Node(T val) {
        this.val = val;
    }

    public static V Instantiate(T val) {
        return (V)Activator.CreateInstance(typeof(V), val);
    }

    public static V FromArray(Nullable<T>[] array) {
        V GetFromArray(int index) {
            if(index >= array.Length || array[index] == null) return null;
            var node = Instantiate((T)array[index]);
            node.left = GetFromArray(index * 2 + 1);
            node.right = GetFromArray(index * 2 + 2);

            return node;
        }

        return GetFromArray(0);
    }

    public Nullable<T>[] ToArray() {
        Nullable<T>[] array = new Nullable<T>[10];

        int AddToArray(Node<T, V> node, int index) {
            if(index >= array.Length) Array.Resize(ref array, array.Length * 2);
            if(node is null) {
                array[index] = null;
                return -1;
            } else {
                int maxSize = index + 1;
                array[index] = node.val;
                maxSize = Math.Max(maxSize, AddToArray(node.left, index * 2 + 1));
                maxSize = Math.Max(maxSize, AddToArray(node.right, index * 2 + 2));

                return maxSize;
            }
        }

        int size = AddToArray(this, 0);
        Array.Resize(ref array, size);

        return array;
    }
}
```

All you do is have you class inherit from this base class and you can make as many Node Trees as you need!

```csharp
public class IntNode: Node<int, IntNode> {
    public IntNode(int val): base(val) { }
}
```

Once you've made your class you can, simple, call the two (2) helper methods to either make a tree from an array or convert your tree to an array.


```csharp
IntNode first = new IntNode(1);
first.left = new IntNode(2);
first.right = new IntNode(3);
first.right.left = new IntNode(4);
first.right.right = new IntNode(5);
           
IntNode second = IntNode.FromArray(new int?[]{ 0, 1, 2, 3, 4, 5, 6, 7 });

Console.WriteLine(String.Join(", ", first.ToArray())); // 1, 2, 3, , , 4, 5
Console.WriteLine(String.Join(", ", second.ToArray())); // 0, 1, 2, 3, 4, 5, 6, 7

Console.WriteLine(second.right.right.val); // 6
Console.WriteLine(IntNode.Instantiate(50).val); // 50
```

Hope this helps you with whatever Node Tree based activities you find yourself doing!