Binary Search Tree Implementation in C#

1. Introduction

A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, referred to as the left and right child. The key property of a BST is that for each node, all nodes in its left subtree have a value less than the node’s value, and all nodes in its right subtree have a value greater than the node’s value. This ensures that elements are always inserted in a sorted order.

2. Implementation Steps

1. Define a Node class to represent individual items in the BST. Each node will have three attributes: Value, Left, and Right.

2. Create a BinarySearchTree class to manage the nodes and operations.

3. Implement basic operations:

- Insert: Add a node to the tree in its sorted position.

- Search: Check if a given value exists in the tree.

- InOrderTraversal: Traverse and display nodes in InOrder sequence (Left, Root, Right).

4. Test the BST with these operations.

3. Implementation in C#

using System;
public class Node {
    public int Value;
    public Node Left;
    public Node Right;
    public Node(int value) {
        this.Value = value;
        this.Left = null;
        this.Right = null;
    }
}
public class BinarySearchTree {
    public Node Root;
    // Insert node to the tree
    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;
    }
    // Check if a value exists in the tree
    public bool Search(int value) {
        return SearchRec(Root, value);
    }
    private bool SearchRec(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (value == root.Value) {
            return true;
        } else if (value < root.Value) {
            return SearchRec(root.Left, value);
        } else {
            return SearchRec(root.Right, value);
        }
    }
    // Traverse and display nodes in InOrder sequence
    public void InOrderTraversal(Node root) {
        if (root != null) {
            InOrderTraversal(root.Left);
            Console.WriteLine(root.Value);
            InOrderTraversal(root.Right);
        }
    }
}
public class Program {
    public static void Main() {
        BinarySearchTree bst = new BinarySearchTree();
        bst.Insert(5);
        bst.Insert(2);
        bst.Insert(8);
        bst.Insert(1);
        bst.Insert(3);
        bst.InOrderTraversal(bst.Root);  // Should print: 1 2 3 5 8
        Console.WriteLine(bst.Search(3)); // Should print: True
        Console.WriteLine(bst.Search(6)); // Should print: False
    }
}

Output:

1
2
3
5
8
True
False

Explanation:

1. The Node class defines the basic structure of each node in the BinarySearchTree. Each node has a Value and potentially two children, Left and Right.

2. The BinarySearchTree class manages the operations related to the tree. The tree is built using a recursive insertion method.

3. The Insert method adds a node to the tree by invoking the private InsertRec method. This method checks the value to be added against the current node's value to determine if it should go left or right.

4. The Search method checks if a given value exists in the tree. It traverses the tree in a manner similar to Insert but stops once it finds the node with the desired value or reaches a null node.

5. The InOrderTraversal method is a recursive method that visits the left child, the current node, and then the right child. This method displays nodes in ascending order, which is the nature of a BST.

6. In the Program class, we create a BinarySearchTree, insert values, perform an InOrder traversal, and search for specific values.

By utilizing this foundational BinarySearchTree implementation, you can further expand upon it with additional methods and features.