In our Previous Articles, we have seen Linked List. Stack, Queue, Graph, etc. In this tutorial, We will implement BST using C#. Binary Search Tree or BST is a special case of a Graph data structure. If you have not familiar with Graph Data Structure , request you to go through it. In this, there will be two children for each node termed as left & right child. When we insert data into a BST we can do based on a condition defined by us. We can solve many problems optimally by implementing solutions using this. We can implement these features using the Iterative way or Recursive way but using the Recursive way will be more intuitive in the case of BST as we can write very minimal & clear code. In this tutorial, we will implement BST using C# with Insert, Search & other useful functionalities.
The Below Image show how a Binary Search Tree looks like.
BST Node using C#
A sample BST Node using C# looks like, We have created a class with 3 properties one will hold the data & the other two will point to the child Nodes.
public class BSTNode
{
public int data;
public BSTNode left;
public BSTNode right;
public BSTNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}Inserting to a BST using C#
In this example we will be storing nodes in right if it is greater than root node else we store it in left child node. We are using recursion to insert a node .
public BSTNode Insert(BSTNode root, int data)
{
if (root == null)
{
root = GetBSTNode(data);
return root;
}
else if (data > root.data)
{
root.right = Insert(root.right, data);
}
else
{
root.left = Insert(root.left, data);
}
return root;
}Traversing a BST using C#
In a BST we have many ways of traversing the nodes but DFS & BFS are the main traversals that are depicted in the above image. In DFS we have 3 types of traversal namely Pre Order, In Order & Post Order. BFS is also known as Level Order Traversal, Here we traverse level by level and left to right. The BST traversal is implemented as below.
DFS
Pre Order
In this , we will print the data first & we will be moving to the left branch and repeating the same.
public void PrintDFS_PreOrder(BSTNode root)
{
if (root == null)
return;
Console.Write(root.data + ",");
PrintDFS_PreOrder(root.left);
PrintDFS_PreOrder(root.right);
}In Order
Here , we will be moving left most branch first m then print the node , after that it will be traversing right branch.
public void PrintDFS_InOrder(BSTNode root)
{
if (root == null)
return;
PrintDFS_InOrder(root.left);
Console.Write(root.data + ",");
PrintDFS_InOrder(root.right);
}Post Order
In Post-Order traversal, we will be covering left and right branch first once we cover that we will be printing the node.
public void PrintDFS_PostOrder(BSTNode root)
{
if (root == null)
return;
PrintDFS_PostOrder(root.left);
PrintDFS_PostOrder(root.right);
Console.Write(root.data + ",");
}BFS Traversal
The BFS traversal of BST is similar to Graph.Here we will be using a Queue to store left & right node of the each node that we visit in order.Below code imple
public void PrintBFS(BSTNode root)
{
Queue<BSTNode> bfsQueue = new Queue<BSTNode>();
bfsQueue.Enqueue(root);
BSTNode current = null;
while (bfsQueue.Any())
{
current = bfsQueue.Peek();
Console.Write(current.data + ",");
if (current.left != null)
bfsQueue.Enqueue(current.left);
if (current.right != null)
bfsQueue.Enqueue(current.right);
bfsQueue.Dequeue();
}
}Searching in BST
By using the BST data structure it is possible to search for an element easily. As we explained in the previous code, we are inserting the data in the right sub-tree if the data is greater than the root, else we will be inserting the data in the left sub-tree. So this will reduce the search time complexity to
O (log n ).
Below is the recursive implementation of code for checking if an element exist in BST. Recursively calling left & right sub tree after comparing it with root element.
public bool IsExists(BSTNode root, int data)
{
if (root == null)
return false;
else if (root.data == data)
return true;
else if (data > root.data)
{
return IsExists(root.right, data);
}
else
{
return IsExists(root.left, data);
}
}Maximum and Minimum using BST
Below code is for finding maximum and minimum . Maximum can be found at right right sub-tree , as we are storing larger element in righ sub-tree.Similarly minimum element can be found at left sub-tree.
public int FindMax(BSTNode root)
{
if (root.right == null)
return root.data;
return FindMax(root.right);
}
public int FindMin(BSTNode root)
{
if (root.left == null)
return root.data;
return FindMin(root.left);
}
The Full Implementation details can be found here.
