C# Binary Search Tree implementation

Question

I have implemented a Binary Search Tree and would really appreciate it if someone could take time to check it and give me feedback.
I try to keep my code clear and simple.

Is it readable?
Is the API of constructors well-designed?
Did I handle the nullable fields of the tree and iterators well?

Please be as strict as possible with me.

Code:

GitHub

TreeNode code:

public class TreeNode
{
    public readonly T Value;

    public TreeNode? LeftLeaf;
    public TreeNode? RightLeaf;

    public TreeNode(T elem)
    {
        Value = elem;
        LeftLeaf = null;
        RightLeaf = null;
    }

    public TreeNode(T elem, TreeNode? left, TreeNode? right) : this(elem)
    {
        LeftLeaf = left;
        RightLeaf = right;
    }
}

BinarySearchTree fields, properties and constructors:

public class BinarySearchTree<T> : ICollection<T>
where T : IComparable<T>
{   
    //TreeNode code 
    //{
    //    see it above
    //}

    public BinarySearchTree()
    {
        Root = null;
        _size = 0;
    }

    public BinarySearchTree(T firstElem)
    {
        Root = new TreeNode(firstElem);
        _size = 0;
    }

    public BinarySearchTree(
        T[] arry, 
        BinarySearchTreeSortOrder order = BinarySearchTreeSortOrder.Ascdending
        Comparer<T>? comparer = null)
    {
        if (arry == null) throw new ArgumentNullException(nameof(arry));
        if (arry.Length == 0) throw new ArgumentException(nameof(arry));

        this.Root = new TreeNode(arry[0]);
        this._size = 1;
    
        _order = order;
        _comparer = comparer;
    }

    // properties
    public int Count => _size;
    public bool IsReadOnly => false;

    // methods
    // Add()    
    // Compare()    
    // Clear()    
    // Contains()     
    // CopyTo()    
    // Min()    
    // Max()    
    // Remove()
    // enumerators section
}

Add method:

/// <summary>
/// Adds an element to the Binary Search Tree in O(n) worse case 
/// and O(log(n)) average case.
/// If the given element already exists in the tree adds a duplicate.
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
    Add(Root, item);
    _size++;
}

// returns the subtree of the given TreeNode that contains new item.
private TreeNode Add(TreeNode? addRoot, T item)
{
    if (addRoot == null) addRoot = new TreeNode(item);
    else
    {
        var cmp = this.Compare(item, addRoot.Value);
        if (cmp <= 0) addRoot.LeftLeaf = Add(addRoot.LeftLeaf, item);
        if (cmp > 0) addRoot.RightLeaf = Add(addRoot.RightLeaf, item);
    }

    return addRoot;
}

Compare method:

private int Compare(T item1, T item2)
{
    int compVal = this._comparer?.Compare(item1, item2) ?? item1.CompareTo(item2);
    return compVal * (_order == BinarySearchTreeSortOrder.Ascdending ? 1 : -1);
}

Clear method:

/// <summary>
/// Clears the BinarySearchTree. Assigns null to the root element.
/// </summary>
public void Clear()
{
    this.Root = null;
    this._size = 0;
}

Contains method:

/// <summary>
/// If BinarySearchTree contains the specified element returns true 
///and false otherwise.
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Contains(T item)
{
    var node = Root;
    while (node != null)
    {
        int cmp = this.Compare(item, node.Value);
        if (cmp < 0) node = node.LeftLeaf;
        else if (cmp > 0) node = node.RightLeaf;
        else return true;
    }

    return false;
}

CopyTo method:

/// <summary>
/// Copies elements of the BinarySearchTree to the specified array in sorted order.
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
    using (var enumerator = this.GetEnumerator(Traversal.InOrder))
    {
        int i = arrayIndex;
        for (int j = 0; j < i; j++) enumerator.MoveNext();
        while (enumerator.MoveNext()) array[i++] = enumerator.Current;
    }
}

Min method:

/// <summary>
/// Extracts the minimal element of the BinarySearchTree in O(1) time.
/// </summary>
/// <returns></returns>
/// <exception cref="NullReferenceException"></exception>
public T Min()
{
    if (Root == null) throw new NullReferenceException(nameof(Root));
    return this.Min(Root).Value;
}

private TreeNode Min(TreeNode minRoot)
{
    while (minRoot.LeftLeaf != null) minRoot = minRoot.LeftLeaf;
    return minRoot;
}

Max method:

/// <summary>
/// Extracts the biggest element of the BinarySearchTree in O(n) worse case 
///and O(log(n)) average case.
/// </summary>
/// <returns></returns>
/// <exception cref="NullReferenceException"></exception>
public T Max()
{
    if (Root == null) throw new NullReferenceException(nameof(Root));
    return this.Max(this.Root).Value;
}

private TreeNode Max(TreeNode maxRoot)
{
    while (maxRoot.RightLeaf != null) maxRoot = maxRoot.RightLeaf;
    return maxRoot;
}

Remove method:

/// <summary>
/// Performs removal of specified item from the BinarySearchTree in O(n) worse
/// case and O(log(n)) average case.
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public bool Remove(T item)
{
    if (!Contains(item)) return false;

    Root = Remove(Root, item);
    _size--;
    return true;
}

private TreeNode? Remove(TreeNode? removeRoot, T item)
{
    if (removeRoot == null) return null;

    var cmp = this.Compare(item, removeRoot.Value);

    if (cmp == 1) removeRoot.RightLeaf = Remove(removeRoot.RightLeaf, item);
    else if (cmp == -1) removeRoot.LeftLeaf = Remove(removeRoot.LeftLeaf, item);
    else
    {
        if (removeRoot.LeftLeaf == null && removeRoot.RightLeaf == null) 
            return null;
        //there are 2 leafs
        if (removeRoot.RightLeaf != null && removeRoot.LeftLeaf != null)
        {
            //find min, replace root with the min and remove min
            var rightMin = Min(removeRoot.RightLeaf);

            rightMin.RightLeaf = Remove(removeRoot.RightLeaf, rightMin.Value);
            rightMin.LeftLeaf = removeRoot.LeftLeaf;
            return rightMin;
        }

        return removeRoot.LeftLeaf ?? removeRoot.RightLeaf;
    }

    return removeRoot;
}

GetEnumerator method:

public IEnumerator<T> GetEnumerator() => GetEnumerator(Traversal.InOrder);

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(Traversal.InOrder);

public IEnumerator<T> GetEnumerator(Traversal traversal)
{
    switch (traversal)
    {
        case Traversal.InOrder: return new InOrderIterator(this);
        case Traversal.PreOrder: return new PreOrderIterator(this);
        case Traversal.LevelOrder: return new LevelOrderIterator(this);
    }

    return new InOrderIterator(this);
}

InOrderEnumerator:

private class InOrderIterator : IEnumerator<T>
{

    private readonly BinarySearchTree<T> _bst;

    private readonly Stack<TreeNode>  _stack = new();

    private TreeNode _trav;
    private TreeNode _current;

    public InOrderIterator(BinarySearchTree<T> bst)
    {
        this._bst = bst ?? throw new NullReferenceException(nameof(bst));
        _trav = bst.Root ?? throw new NullReferenceException(nameof(bst.Root));
        _stack.Push(bst.Root);
        _current = bst.Root;
    }
    
    public bool MoveNext()
    {
        if (_stack.Count == 0) return false;

        while (_trav.LeftLeaf != null)
        {
            _stack.Push(_trav.LeftLeaf);
            _trav = _trav.LeftLeaf;
        }

        _current = _stack.Pop();

        if (_current.RightLeaf != null)
        {
            _stack.Push(_current.RightLeaf);
            _trav = _current.RightLeaf;
        }

        return true;
    }

    public void Reset()
    {
        if (_bst.Root != null)
        {
            _trav = _bst.Root;
            _stack.Push(_bst.Root);
        }
    }

    public T Current => _current.Value;

    object IEnumerator.Current => Current;

    public void Dispose()
    {
        /*throw new NotImplementedException();*/
    }
}

PreOrderEnumerator:

private class PreOrderIterator : IEnumerator<T>
{
    private readonly BinarySearchTree<T> _bst;

    private readonly Stack<TreeNode> _stack = new();

    private TreeNode _current;

    public PreOrderIterator(BinarySearchTree<T> bst)
    {
        this._bst = bst ?? throw new NullReferenceException(nameof(bst));
        _current = bst.Root ?? throw new NullReferenceException(nameof(bst.Root));
        _stack.Push(bst.Root);
    }
    public T Current => _current.Value;

    object IEnumerator.Current => throw new NotImplementedException();

    public void Dispose()
    {
        //throw new NotImplementedException();
    }

    public bool MoveNext()
    {
        if (_stack.Count == 0) return false;
        _current = _stack.Pop();
        if (_current.RightLeaf != null) _stack.Push(_current.RightLeaf);
        if (_current.LeftLeaf != null) _stack.Push(_current.LeftLeaf);
        return true;
    }

    public void Reset()
    {
        if (_bst.Root != null)
        {
            _stack.Clear();
            _stack.Push(_bst.Root);
        }
    }
}

LevelOrderEnumerator:

private class LevelOrderIterator : IEnumerator<T>
{
    private BinarySearchTree<T> _bst;

    private Queue<TreeNode> _queue = new();

    private TreeNode _current;

    public LevelOrderIterator(BinarySearchTree<T> bst)
    {
        this._bst = bst ?? throw new ArgumentNullException(nameof(bst));

        if (bst.Root == null) 
            throw new NullReferenceException($"{nameof(bst.Root)} is null.");

        _current = new TreeNode(bst.Root.Value, 
                                bst.Root.LeftLeaf,
                                bst.Root.RightLeaf);

        _queue.Enqueue(bst.Root);
    }
    
    public bool MoveNext()
    {
        if (_queue.Count == 0) return false;

        _current = _queue.Dequeue();

        if (_current.LeftLeaf != null) _queue.Enqueue(_current.LeftLeaf);
        if (_current.RightLeaf != null) _queue.Enqueue(_current.RightLeaf);

        return true;
    }

    public void Reset()
    {
        if (_bst.Root != null)
        {
            _queue.Clear();
            _queue.Enqueue(_bst.Root);
        }
    }

    public T Current => _current.Value;

    object IEnumerator.Current => throw new NotImplementedException();

    public void Dispose()
    {
        //throw new NotImplementedException();
    }
}

Declared outside of the BinarySearchTree

Traversal type:

public enum Traversal
{
    InOrder,
    PreOrder,
    LevelOrder,
    PostOrder
}

Sort order:

public enum BinarySearchTreeSortOrder
{
    Ascdending,
    Descending
}

Rick Davin · Accepted Answer · 2022-07-22 15:58:13Z

My apologies that I do not have enough time to review the entire code, but I do have remarks about the stuff towards the top.

Class TreeNode

I would alter the constructors differently than what you show. What you have is nice enough, and I do struggle on whether this is my personal preference or a better design, so I offer this an an alternative.

public TreeNode(T elem) : this(elem, null, null)
{ }

public TreeNode(T elem, TreeNode? left, TreeNode? right)
{
    Value = elem;
    LeftLeaf = left;
    RightLeaf = right;
}

BinarySearchTree contructor #2

public BinarySearchTree(T firstElem)
{
    Root = new TreeNode(firstElem);
    _size = 0;
}

Should that be _size = 1; ???

BinarySearchTree contructor #3

What you have:

public BinarySearchTree(
    T[] arry, 
    BinarySearchTreeSortOrder order = BinarySearchTreeSortOrder.Ascdending
    Comparer<T>? comparer = null)
{
    if (arry == null) throw new ArgumentNullException(nameof(arry));
    if (arry.Length == 0) throw new ArgumentException(nameof(arry));

    this.Root = new TreeNode(arry[0]);
    this._size = 1;

    _order = order;
    _comparer = comparer;
}

Observations:

You restrict the input to be an array of T. It would be more flexible is you allowed it to be IList<T>. It would be even more flexible if you allowed it to be IEnumerable<T>. If you do use enumerable, then you also have to change checks for Length or grabbing index [0].

You seem to only set the Root with the first element in the array, and then do nothing with remaining elements. What if someone passes in a 5 element collection?

Here's a short (imperfect) stub demonstrating using enumerable input:

public BinarySearchTree(
    IEnumerable<T> elements, 
    BinarySearchTreeSortOrder order = BinarySearchTreeSortOrder.Ascdending
    Comparer<T>? comparer = null)
{
    if (elements == null) throw new ArgumentNullException(nameof(elements));
    if (!elements.Any()) throw new ArgumentException(nameof(elements));

    this.Root = new TreeNode(elements.First());
    this._size = 1;

    _order = order;
    _comparer = comparer;

    // To process more elements, use something like:
    foreach (var element in elements.Skip(1))
    {
         // do something
    }

}

\$\begingroup\$ Thanks a lot for your feedback! \$\endgroup\$

Kirill Dolghi
– Kirill Dolghi

2022-07-22 16:10:04 +00:00
Commented Jul 22, 2022 at 16:10 — Kirill Dolghi
– Kirill Dolghi, Commented Jul 22, 2022 at 16:10
\$\begingroup\$ (If not learning just C#, but OO design&coding: Well done!) \$\endgroup\$

greybeard
– greybeard

2022-07-23 17:24:50 +00:00
Commented Jul 23, 2022 at 17:24 — greybeard
– greybeard, Commented Jul 23, 2022 at 17:24

greybeard · Accepted Answer · 2022-07-23 17:25:04Z

A pity you didn't present the class summary the GitHub repository contains.
One thing I'd move up there is the enumeration of methods presented above at the end of class BinarySearchTree<T>.
Pretty much constituting the interface, which I consider neat
(but for the mention of inconsequential internal detail:
storage - not presented above
existence&handling of Root).
(Rick Davin has an excellent point about "the powerful" constructor.
Where there is a non-negligible chance of the elements of the enumerable being ordered, one might better adapt the order of processing.)

Possible changes include PostOrderIterator and reverse traversals.
The latter would allow to ignore the difference between ascending and descending everywhere but in the iterators. Having an array of children might help avoiding code duplication.

What you call leaf is conventionally called child -
a leaf is a node with no children.
(Ascdending contains a typo - less of an issue given rename.
And among the cases worse than the average, worst usually gets mentioned.)

The summary of T Min() specifies O(1) time -
the implementation doesn't support that (see T Max()).
(Empty SGML tags can be denoted <returns/>.)

It should be possible to avoid the call to Contains() in bool Remove(T item) -
nothing that came to my mind would be as readable.

Stack Exchange Network

C# Binary Search Tree implementation

2 Answers 2

You must log in to answer this question.

Hot Network Questions

C# Binary Search Tree implementation

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions