Skip to content

Instantly share code, notes, and snippets.

@NovemberDev
Last active March 22, 2021 10:31
Show Gist options
  • Save NovemberDev/887f7cc1f33ec96c50878bbedd78770a to your computer and use it in GitHub Desktop.
Save NovemberDev/887f7cc1f33ec96c50878bbedd78770a to your computer and use it in GitHub Desktop.
Generic Binary Tree implementation I built
using System;
using System.Collections.Generic;
// Author: NovemberDev
public class Program
{
///
/// TreeNode baseclass
///
public class TreeNode<T>
{
/// This TreeNode's Value
public T Value;
/// This TreeNode's ParentNode
public TreeNode<T> Parent;
/// This TreeNode's ChildNodes
public List<TreeNode<T>> Children = new List<TreeNode<T>>();
/// Creates a new TreeNode with an initial value and an amount of ChildNodes to parent
/// during construction
public TreeNode(T initialValue, params TreeNode<T>[] childNodes)
{
Value = initialValue;
foreach(TreeNode<T> childNode in childNodes)
AddChild(childNode);
// Note: the params can be removed in favor of a left and right ChildNode approach but
// I like to leave it as it is, since you can then customize it to hold as many children
// as you need there to be, make sure to remove the exception in AddChild as well
}
/// Recursively returns the leaf TreeNode by taking in a comparison function,
/// which compares all children
public TreeNode<T> Traverse(Func<TreeNode<T>, TreeNode<T>, bool> comparisonFunction)
{
if(Children.Count < 1)
return this;
TreeNode<T> currentNode = null;
foreach(TreeNode<T> childNode in Children)
{
if(currentNode == null)
{
currentNode = childNode;
continue;
}
if(comparisonFunction.Invoke(currentNode, childNode))
currentNode = childNode;
}
Console.WriteLine("Traverse -> " + currentNode.Value);
return currentNode.Traverse(comparisonFunction);
}
/// Recursively returns the Root-TreeNode
public TreeNode<T> TraverseToRoot()
{
if(Parent != null)
return Parent.TraverseToRoot();
return this;
}
/// Adds a child and sets it's Parent property to the current TreeNode
/// Throws an exception if more than 2 children exist
public void AddChild(TreeNode<T> childNode)
{
childNode.Parent = this;
if(Children.Count > 1)
throw new ArgumentOutOfRangeException("TreeNode cannot hold more than 2 ChildNodes");
Children.Add(childNode);
}
// Check if TreeNode is a child node
public bool IsLeaf()
{
return Children.Count == 0;
}
/// Check if TreeNode is a root node
public bool IsRoot()
{
return Parent == null;
}
}
public static void Main()
{
TreeNode<int> rootNode = new TreeNode<int>(
100,
new TreeNode<int>(
10,
new TreeNode<int>(
5,
new TreeNode<int>(2),
new TreeNode<int>(3)
),
new TreeNode<int>(
2,
new TreeNode<int>(2),
new TreeNode<int>(3)
)
),
new TreeNode<int>(
11,
new TreeNode<int>(
1,
new TreeNode<int>(5),
new TreeNode<int>(6)
),
new TreeNode<int>(
3,
new TreeNode<int>(7),
new TreeNode<int>(8)
)
)
);
TreeNode<int> leafNode = rootNode.Traverse((t1, t2) => t1.Value < t2.Value);
Console.WriteLine("Result = " + leafNode.Value);
Console.WriteLine("Root = " + leafNode.TraverseToRoot().Value);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment