C# Data Structures and Algorithms

Insertion

The next necessary operation is insertion of a node into a BST. Such a task is a bit more complicated, because you need to find a place for adding a new element that will not violate the BST rules. Let's take a look at the code of the Add method:

public void Add(T data) 
{ 
    BinaryTreeNode<T> parent = GetParentForNewNode(data); 
    BinaryTreeNode<T> node = new BinaryTreeNode<T>()  
        { Data = data, Parent = parent }; 
 
    if (parent == null) 
    { 
        Root = node; 
    } 
    else if (data.CompareTo(parent.Data) < 0) 
    { 
        parent.Left = node; 
    } 
    else 
    { 
        parent.Right = node; 
    } 
 
    Count++; 
} 

The method takes one parameter, a value that should be added to the tree. Within the method, you find a parent element (using the GetParentForNewNode auxiliary method), where a new node ...