Implementing a Binary Tree in C#
Hello! Today, I wanted to go over one of the classic data structures: the binary tree. Whether you’re brushing up on algorithms for interviews (these come up a lot!) or building a custom solution, understanding how to implement a binary tree in C# is a valuable skill. In this post, I’ll walk you through creating a binary tree, including node insertion and a few traversal methods, with clean, idiomatic C# code. For your convenience, I have also put all of the code into a folder in the DotNetDigestCodeSamples repository on GitHub. The link for that folder is here.
What Is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children, called the left and right child. It’s useful for tasks like searching, sorting, or representing hierarchical data. Today, we’ll implement a binary search tree (BST), which is a special kind of binary tree. The left child’s value is less than the parent’s, and the right child’s value is greater than the parent’s.
Our goals:
Define a Node class and a BinaryTree class.
Implement insertion.
Add methods for in-order, pre-order, and post-order traversal.
Keep the code simple and reusable.
Step 1: Defining the Node and BinaryTree Classes
Let’s start with the basic structure. Each node in our tree will hold a value and references to its left and right children. We’ll use a generic type T to make the tree flexible, with the constraint that T must implement IComparable<T> for ordering in the BST.
public class Node<T> where T : IComparable<T>
{
public T Value { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public Node(T value)
{
Value = value;
Left = null;
Right = null;
}
}
public class BinaryTree<T> where T : IComparable<T>
{
public Node<T> Root { get; private set; }
public BinaryTree()
{
Root = null;
}
}The Node<T> class stores the value and references to child nodes. The BinaryTree<T> class keeps track of the root node and provides a clean entry point for operations.
Step 2: Inserting Nodes
In a BST, insertion follows a simple rule: compare the new value with the current node’s value. If it’s smaller, go left; if it’s larger, go right. If we hit a null spot, that’s where the new node goes. Let’s implement an Insert method.
public void Insert(T value)
{
Root = InsertRec(Root, value); // i.e. insert recursive
}
private Node<T> InsertRec(Node<T> node, T value)
{
if (node == null)
{
return new Node<T>(value);
}
if (value.CompareTo(node.Value) < 0)
{
node.Left = InsertRec(node.Left, value);
}
else if (value.CompareTo(node.Value) > 0)
{
node.Right = InsertRec(node.Right, value);
}
return node;
}This recursive approach keeps the code clean. The public Insert method starts at the root, and the private InsertRec method handles the recursion. If the value equals the current node’s value, we skip insertion to avoid duplicates. If you wish to modify this to accept duplicates, you may.
Step 3: Traversing the Tree
Tree traversal is a great way to visit all nodes, and there are three common depth-first traversal methods:
In-order: Left, Root, Right (produces sorted order for a BST).
Pre-order: Root, Left, Right.
Post-order: Left, Right, Root.
Let’s add methods to print the tree using these traversals. For simplicity, we’ll return the values as a list.
public List<T> InOrderTraversal()
{
var result = new List<T>();
InOrderRec(Root, result);
return result;
}
private void InOrderRec(Node<T> node, List<T> result)
{
if (node != null)
{
InOrderRec(node.Left, result);
result.Add(node.Value);
InOrderRec(node.Right, result);
}
}
public List<T> PreOrderTraversal()
{
var result = new List<T>();
PreOrderRec(Root, result);
return result;
}
private void PreOrderRec(Node<T> node, List<T> result)
{
if (node != null)
{
result.Add(node.Value);
PreOrderRec(node.Left, result);
PreOrderRec(node.Right, result);
}
}
public List<T> PostOrderTraversal()
{
var result = new List<T>();
PostOrderRec(Root, result);
return result;
}
private void PostOrderRec(Node<T> node, List<T> result)
{
if (node != null)
{
PostOrderRec(node.Left, result);
PostOrderRec(node.Right, result);
result.Add(node.Value);
}
}Each traversal method uses a recursive helper to build a list of values in the specified order. You can easily modify these to perform other actions (e.g., printing directly).
Step 4: Testing the Binary Tree
Let’s put it all together with a quick test in a console app to see the tree in action.
class Program
{
static void Main()
{
var tree = new BinaryTree<int>();
tree.Insert(5);
tree.Insert(3);
tree.Insert(7);
tree.Insert(1);
tree.Insert(9);
Console.WriteLine("In-Order Traversal: " + string.Join(", ", tree.InOrderTraversal()));
Console.WriteLine("Pre-Order Traversal: " + string.Join(", ", tree.PreOrderTraversal()));
Console.WriteLine("Post-Order Traversal: " + string.Join(", ", tree.PostOrderTraversal()));
}
}Expected output:
In-Order Traversal: 1, 3, 5, 7, 9
Pre-Order Traversal: 5, 3, 1, 7, 9
Post-Order Traversal: 1, 3, 9, 7, 5This creates a BST with values 5, 3, 7, 1, and 9, then prints the traversals. The in-order traversal confirms the values are sorted, as expected for a BST.
Tips for Extending the Binary Tree
Want to take this further? Here are a few ideas:
Search: Add a method to check if a value exists in the tree.
Delete: Implement node deletion, handling cases for nodes with zero, one, or two children.
Balance: Modify the tree to support self-balancing (e.g., AVL or Red-Black trees).
Non-recursive: Rewrite insertion or traversal using iteration and a stack/queue.
Wrapping Up
We’ve built a simple yet functional binary search tree in C#, complete with insertion and three different traversal methods. This implementation is a great foundation for learning. For more complicated applications, consider edge cases like duplicate values or thread safety, depending on your needs.
I hope this helps you understand binary trees better. Take care!