Artem

Posted on

# C# - Generic Class To Create Node Tree From Array

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...

``````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!

``````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;
}
}

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!

``````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.

``````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!