C# program to implement binary search tree

Here's an example of a C# program that implements a binary search tree (BST):

using System;

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

    public Node(int data)
    {
        Data = data;
        Left = null;
        Right = null;
    }
}

class BinarySearchTree
{
    private Node root;

    public void Insert(int data)
    {
        root = InsertRecursive(root, data);
    }

    private Node InsertRecursive(Node current, int data)
    {
        if (current == null)
        {
            return new Node(data);
        }

        if (data < current.Data)
        {
            current.Left = InsertRecursive(current.Left, data);
        }
        else if (data > current.Data)
        {
            current.Right = InsertRecursive(current.Right, data);
        }

        return current;
    }

    public bool Search(int data)
    {
        return SearchRecursive(root, data);
    }

    private bool SearchRecursive(Node current, int data)
    {
        if (current == null)
        {
            return false;
        }

        if (data == current.Data)
        {
            return true;
        }

        if (data < current.Data)
        {
            return SearchRecursive(current.Left, data);
        }

        return SearchRecursive(current.Right, data);
    }

    public void InorderTraversal()
    {
        InorderTraversalRecursive(root);
        Console.WriteLine();
    }

    private void InorderTraversalRecursive(Node current)
    {
        if (current != null)
        {
            InorderTraversalRecursive(current.Left);
            Console.Write(current.Data + " ");
            InorderTraversalRecursive(current.Right);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree bst = new BinarySearchTree();

        // Inserting elements into the binary search tree
        bst.Insert(50);
        bst.Insert(30);
        bst.Insert(20);
        bst.Insert(40);
        bst.Insert(70);
        bst.Insert(60);
        bst.Insert(80);

        // Performing inorder traversal of the binary search tree
        Console.WriteLine("Inorder Traversal of the Binary Search Tree:");
        bst.InorderTraversal();

        // Searching for elements in the binary search tree
        int searchElement = 40;
        if (bst.Search(searchElement))
        {
            Console.WriteLine($"{searchElement} is found in the binary search tree.");
        }
        else
        {
            Console.WriteLine($"{searchElement} is not found in the binary search tree.");
        }
    }
}

This program creates a binary search tree class ('BinarySearchTree') that contains a private 'Node' class. The 'Node' class represents each node in the binary search tree and holds the data, and references to the left and right child nodes.

The 'BinarySearchTree' class provides three methods: 'Insert', 'Search', and 'InorderTraversal'. The 'Insert' method inserts a new node with the given data into the binary search tree. The 'Search' method searches for a given data in the binary search tree. The 'InorderTraversal' method performs an inorder traversal of the binary search tree and prints the elements in sorted order.

In the 'Main method', we create an instance of 'BinarySearchTree', insert elements into the binary search tree using the 'Insert' method, perform an inorder traversal of the binary search tree using the 'InorderTraversal' method, and search for a specific element using the 'Search' method.

Inorder Traversal of the Binary Search Tree:
20 30 40 50 60 70 80
40 is found in the binary search tree.

This indicates that the binary search tree was successfully implemented, and the inorder traversal of the tree produced the sorted order of elements. Additionally, the program confirms that the element 40 is present in the binary search tree.