Basic Binary search tree (BST) implementation (Without recursion)

Binary search tree creation and insertion using a single loop. A binary search tree (BST) is a hierarchical data structure where each node has at most two child nodes. Follow these steps to implement and insert data into a binary search tree.

Definition for BST

A binary search tree (BST) is a binary tree data structure where each node has at most two child nodes, referred to as the left child and the right child. The key property of a binary search tree is that for each node, all elements in its left subtree are less than its value, and all elements in its right subtree are greater than its value. This property allows for efficient searching, insertion, and deletion operations." - Source Chat GPT.

Let's start the implementation.

Step 1. Create a node class.

public class Node
{
    public int Data { get; set; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int val)
    {
        Data = val; 
    }
}

Step 2. Create a BinarySearchTree class.

public class BinarySearchTree
{
    private readonly Node _root;
    public BinarySearchTree(int value)
    {
        _root = new Node(value);
    }

    public Node Root
    {
        get { return _root; }
    }
}

So far we have just created the structure of the a binary tree.

Step 3. To make sure the binary search tree implementation we need to ensure the data is proper while inserting it into nodes. Make sure left node is always less than root node and right node is greater than root node. Add Insert() method in BinarySearchTree.cs class.

public class BinarySearchTree
{
    private readonly Node _root;
    public BinarySearchTree(int value)
    {
        _root = new Node(value);
    }

    public Node Root
    {
        get { return _root; }
    }

    public void Insert(int value)
    {
        Node currentNode = _root;
        Node parent = _root;

        while (currentNode != null)
        {
            parent = currentNode;
            if (value < currentNode.Data)
            {
                currentNode = currentNode.Left;
            }
            else
            {
                currentNode = currentNode.Right;
            }
        }

        if (value < parent.Data)
        {
            parent.Left = new Node(value);
        }
        else
        {
            parent.Right = new Node(value);
        }
    }
}

That's it we are ready with our first binary search tree. Time to insert some data in out BST.

BinarySearchTree binarySearchTree = new BinarySearchTree(12);
binarySearchTree.Insert(3);
binarySearchTree.Insert(442);
binarySearchTree.Insert(2);
binarySearchTree.Insert(78);
binarySearchTree.Insert(-90);
binarySearchTree.Insert(55);
binarySearchTree.Insert(90);

The above data will look like following.

You may see the data while debugging you code in IDE.