Let's implement a Binary Search Tree

on Let's Implement, C#

A binary search tree is a classic data structure with some pretty great properties; namely O(log(n)) search, insert, and deletion performance.

Let's implement one from scratch.

First, we need a class to represent each node in our tree.

public class Node
{
    public Node Left { get; set; }
    public Node Right { get; set; }
    public object Value { get; set; }
    public int Key { get; set; }
}

For my implementation, I want to be able to add arbitrary objects to my tree; therefore, I'm segregating the object reference stored from the key used to order it.

Let's implement the skeleton of the tree itself.

public class BinarySearchTree
{
    Node _root;

    public bool Add(int key, object value)
    {
        if (null == _root)
        {
            _root = new Node()
            {
                Key = key,
                Value = value
            };

            return true;
        }

        return _root.Add(key, value);
    }
}

We'll need an Add() method on our Node class; let's add that.

public bool Add(int key, object value)
{
    if (this.Key == key)
        return false; // Cannot add the same key twice

    if (this.Key < key)
    {
        // The specified key is less than the current key; place node on the left of this node
        if (null == Left)
        {
            Left = new Node()
            {
                Key = key,
                Value = value
            };
            return true;
        }
        else
        {
            // Left already has a node.
            return Left.Add(key, value);
        }
    } 
    else if (Key > key)
    {
        // The specified key is more than the current key; place node on the right of this node
        if (null == Right)
        {
            Right = new Node()
            {
                Key = key,
                Value = value
            };
            return true;
        }
        else
        {
            // Right already has a node.
            return Right.Add(key, value);
        }
    }

    throw new InvalidOperationException("Something horrible happened.");
}

Note the last line - we're handling all cases of possible key comparisons for the passed key and current node's key, so if we actually manage to fail all the provided comparisons and reach the end of the method, something horrible happened.

In all likelihood, the horrible thing that happened was someone attempted to manipulate our BST implementation from multiple threads simultaneously. Our implementation isn't thread-safe. That's future-post fodder.

Okay, we can Add nodes. Let's give it a spin.

static void Main(string[] args)
{
    var bst = new BinarySearchTree();

    bst.Add(1, "one");
    bst.Add(45, "forty-five");
    bst.Add(13, "thirteen");
    bst.Add(33, "thirty-three");
}

At the end of this, we should wind up with a tree that looks like:

First Execution BST Visualization

Next up, we'll implement searching, deletion, and tests to verify that our tree behaves correctly.

comments powered by Disqus