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;
}
}
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!
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!
Top comments (0)