Although the underlying data structures behind SortedDictionary<TKey, TValue> and SortedList<TKey, TValue> (in the System.Collections.Generic namespace) are binary search trees, there is a surprising absence of a BST-based collection from the .NET Framework. If one only wishes to store a series of unkeyed values, an IDictionary-based collection seems like overkill. The aforementioned classes also have the limitation of being unable to store duplicate keys.
With that in mind, I decided to implement a simple generic binary search tree in C#.
My objectives for this were as follows:
- O(1) performance for Count and Clear()
- O(log n) performance for Add(), Remove() and Contains() (assuming unsorted/random insertions)
- In-order (sorted) iteration with foreach
- Allow duplicate elements
- Completely abstracted implementation (i.e. nodes are invisible to the caller, appears to be a sorted collection of elements only)
Since BSTs have a deterministic order with no indexing, the most relevant collection interface to implement is ICollection<T>. In addition to the methods and properties defined in the interface, I also want to provide a reverse iterator and a way of cloning the content (and structure) of the tree. The public face of the class is shown below:
Note that the inner class, BSTNode, is private. It cannot be accessed from outside the scope of the collection. This is intentional; I want to avoid the clunkiness of the built-in LinkedList<T> class, which exposes its nodes as a public type and returns references to them. Internally, each node holds three references; to the lesser/greater nodes and to the parent node. The latter simplifies the Remove() operation and the traversal algorithm.
GetEnumerator() is hooked up to the InOrder property, which uses an iterator block to traverse the tree in-order (i.e. left subtree, node, right subtree). Since Add() performs an insertion sort, this traversal strategy ensures a sorted iteration. ReverseOrder is provided for use with the foreach statement, while PreOrder (i.e. node, left subtree, right subtree) can be used to clone the structure of the tree – its output can be fed directly into Add() to preserve the distribution of nodes in the tree. Tree traversal is commonly implemented using recursion, but this puts a cap on the maximum number of elements (due to the inevitability of encountering a StackOverflowException). To avoid this, a less elegant (but more memory-friendly) looping algorithm has been used (courtesy of this post by Haroon Saeed).
Remove() takes into account the three possible permutations for removing nodes while maintaining sort order:
- A leaf node is simply unlinked.
- A node with one child is replaced by its child (removed node’s parent links to the removed node’s child and vice-versa).
- For a node with two children, first the successor node is identified (i.e. the element with the lowest value within the “greater-than subtree”). The removed node’s value is replaced with the successor node’s value and then the old successor is removed according to rule #2.
The Count property is an internal field that is incremented/decremented as part of the insertion/deletion algorithms.
Example Usage
// construct and populate a BST of integers (random order) BST<int> test = new BST<int>(new int[] { 12, 1, 8, 200, 657, 50, 2, 9, 13, 1024, 512, 768 }); // display the elements by traversing in-order foreach (int val in test) Console.Write("{0} ", val); Console.WriteLine(); // alter the tree test.Add(10); test.Add(80); test.Remove(12); // test the binary search Console.WriteLine("'12' is " + (!test.Contains(12) ? "NOT " : "") + "in the collection."); Console.WriteLine("'10' is " + (!test.Contains(10) ? "NOT " : "") + "in the collection."); // display the new elements in reverse order foreach (int val in test.ReverseOrder) Console.Write("{0} ", val); Console.WriteLine();