Let's implement a Binary Search Tree, Part II

on Let's Implement, C#

For part one, check out Let's implement a Binary Search Tree

Last up, we defined our tree:

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);
    }
}

And our tree would contain nodes:

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

    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.");
    }
}

Let's implement searching.

Let's define a search method on our node class that'll be called recursively:

public bool Search(int searchKey, out object value)
{
    value = null;

    if (Key == searchKey)
    {
        value = Value;
        // Hey! It's us!
        return true;
    }

    if (Key < searchKey)
    {
        if (Left == null)
        {
            return false;
        }

        return Left.Search(searchKey, out value);
    }

    if (Key > searchKey)
    {
        if (Right == null)
        {
            return false;
        }

        return Right.Search(searchKey, out value);
    }

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

Now, let's implement search on the tree itself to kick things off.

public bool Search(int searchKey, out object value)
{
    value = null;

    return _root != null && _root.Search(searchKey, out value);
}

When the user calls Search(...) on our BST object, we'll kick off a call to the root node's Search(...) method if it's not null. If it is null, we'll just return false. Each node will check to see if it matches the desired searchKey - if it does, it'll return true, and set the value out parameter equal to the object stored on that node.

Let's try it out.

class Program
{
    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");

        object foundValue = null;

        bst.Search(33, out foundValue);
        Console.WriteLine("Found Value: {0}", foundValue);

        bst.Search(1, out foundValue);
        Console.WriteLine("Found Value: {0}", foundValue);

        bst.Search(13, out foundValue);
        Console.WriteLine("Found Value: {0}", foundValue);

        bst.Search(45, out foundValue);
        Console.WriteLine("Found Value: {0}", foundValue);
    }
}

Our labors now produce the following output:

Found Value: thirty-three
Found Value: one
Found Value: thirteen
Found Value: forty-five

Looks perfect.

Next up, we'll implement the slightly more complex gesture of deletion followed by tests.

comments powered by Disqus