How to Implement Binary Search Tree in C# - Simple Guide

To implement a Binary Search Tree in C#, define a Node class with left and right child references and a value. Then create a BinarySearchTree class with methods to insert nodes and traverse the tree in order.

Syntax

A binary search tree consists of nodes where each node has a value and references to left and right child nodes. The Node class holds the data and links. The BinarySearchTree class manages the root node and provides methods like Insert and InOrderTraversal.

• Node class: stores the value and pointers to children.
• Insert method: adds values maintaining BST order (left < node < right).
• Traversal method: visits nodes in sorted order.

csharp

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinarySearchTree
{
    public Node Root;

    public BinarySearchTree()
    {
        Root = null;
    }

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }

        if (value < root.Value)
            root.Left = InsertRec(root.Left, value);
        else if (value > root.Value)
            root.Right = InsertRec(root.Right, value);

        return root;
    }

    public void InOrderTraversal(Node root)
    {
        if (root != null)
        {
            InOrderTraversal(root.Left);
            System.Console.Write(root.Value + " ");
            InOrderTraversal(root.Right);
        }
    }
}

Example

This example shows how to create a binary search tree, insert values, and print them in sorted order using in-order traversal.

csharp

using System;

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinarySearchTree
{
    public Node Root;

    public BinarySearchTree()
    {
        Root = null;
    }

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }

        if (value < root.Value)
            root.Left = InsertRec(root.Left, value);
        else if (value > root.Value)
            root.Right = InsertRec(root.Right, value);

        return root;
    }

    public void InOrderTraversal(Node root)
    {
        if (root != null)
        {
            InOrderTraversal(root.Left);
            Console.Write(root.Value + " ");
            InOrderTraversal(root.Right);
        }
    }
}

class Program
{
    static void Main()
    {
        BinarySearchTree bst = new BinarySearchTree();
        bst.Insert(50);
        bst.Insert(30);
        bst.Insert(70);
        bst.Insert(20);
        bst.Insert(40);
        bst.Insert(60);
        bst.Insert(80);

        Console.WriteLine("In-order traversal of the BST:");
        bst.InOrderTraversal(bst.Root);
    }
}

Output

In-order traversal of the BST:
20 30 40 50 60 70 80 

Common Pitfalls

Common mistakes when implementing a binary search tree include:

• Not handling the case when the tree is empty (root is null).
• Inserting duplicate values without a clear rule (usually duplicates are ignored or placed consistently).
• Incorrectly linking nodes, causing infinite loops or broken tree structure.
• Forgetting to update the root when inserting the first node.

Always use recursion or iteration carefully to maintain the BST property.

csharp

/* Wrong: Not updating root on first insert */
public void InsertWrong(int value)
{
    if (Root == null)
    {
        Node newNode = new Node(value);
        // Forgot to assign Root = newNode;
    }
    else
    {
        // Insert logic
    }
}

/* Correct: Update root properly */
public void InsertCorrect(int value)
{
    Root = InsertRec(Root, value);
}

Quick Reference

• Node class: Holds value and left/right children.
• Insert method: Recursively adds nodes maintaining order.
• InOrderTraversal: Prints nodes in ascending order.
• Root: Starting point of the tree.

Key Takeaways

Define a Node class with value and left/right child references.

Use recursion to insert nodes while maintaining BST order.

Perform in-order traversal to visit nodes in sorted order.

Always update the root when inserting the first node.

Avoid duplicates or handle them consistently.