A Quick and Dirty Binary Search Tree in C#

I’ve been coding mostly with C# for the past eight years and I’ve never needed a binary search tree until this week. So I coded up an implementation that is very simple, quite crude, but effective for my purposes. For kicks I decided to implement all methods using recursion. My personal rule of thumb is to avoid recursive code as much as possible but this time I deliberately used recursion, mostly just to stay in practice. The recursive Delete method was especially ugly. Calling my tree code looks like:

BinarySearchTree bst = new BinarySearchTree();

Console.WriteLine(“Inserting 10-90 in scrambled order”);
bst.Insert(50);
bst.Insert(20);
bst.Insert(70);
bst.Insert(10);
bst.Insert(30);
bst.Insert(60);
bst.Insert(90);
bst.Insert(40);
bst.Insert(80);

Console.Write(“Tree is: “);
bst.Display();
Console.WriteLine(“\nCount = ” + bst.Count);
Console.WriteLine(“Height = ” + bst.Height());
Console.WriteLine(“50? ” + bst.IsThere(50));
Console.WriteLine(“90? ” + bst.IsThere(90));

Console.WriteLine(“\nDeleting 50 and 30”);
bst.Delete(50);
bst.Delete(30);

Console.Write(“Tree is: “);
bst.Display();
Console.WriteLine(“\nCount = ” + bst.Count);
Console.WriteLine(“Height = ” + bst.Height());
Console.WriteLine(“50? ” + bst.IsThere(50));
Console.WriteLine(“90? ” + bst.IsThere(90));

The class definition skeleton is:

public class BinarySearchTree
{
  private class TreeNode
  {
    public long data;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(long valu) { this.data = valu;
      left = null; right = null;
    }
    public override string ToString() { return this.data.ToString(); }

  }

  private TreeNode root;
  private int count;

  public BinarySearchTree()
  {
    this.root = null; this.count = 0;
  }

  public int Count { get { return this.count; } }

  // Insert, Delete, Display, IsThere
}

The recursive Insert method is:

public void Insert(long valu) // public interface to recursive worker
{
  if (IsThere(valu) == false) // do not allow dups
    Insert(ref this.root, valu);
}

private void Insert(ref TreeNode rootNode, long valu)
{
  if (rootNode == null)
  {
    TreeNode newNode = new TreeNode(valu);
    rootNode = newNode;
    ++this.count;
  }
  else if (valu < rootNode.data)
    Insert(ref rootNode.left, valu);
  else
    Insert(ref rootNode.right, valu);
}

The recursive IsThere method is:

public bool IsThere(long valu) // public interface
{
  return IsThere(this.root, valu);
}

private bool IsThere(TreeNode rootNode, long valu) // recursive worker
{
  if (rootNode == null)
    return false;
  else if (rootNode.data == valu)
    return true;
  else if (valu < rootNode.data)
    return IsThere(rootNode.left, valu);
  else
    return IsThere(rootNode.right, valu);
}

The recursive Display method is:

 

public void Display() // public interface
{
  Display(this.root);
}

private void Display(TreeNode rootNode) // private recursive worker
{
  if (rootNode != null)
  {
    Display(rootNode.left); // inorder traversal
    Console.Write(rootNode.ToString() + ” “);
    Display(rootNode.right);
  }
}

The recursive Delete method is:

public void Delete(long valu)
{
  if (IsThere(valu) == true)
  {
    Delete(ref this.root, valu);
    –this.count;
  }
}
private void Delete(ref TreeNode rootNode, long valu)
{
  if (rootNode != null)
  {
    if (valu < rootNode.data)
      Delete(ref rootNode.left, valu);
    else if (valu > rootNode.data)
      Delete(ref rootNode.right, valu);
    else // valu == rootNode.data
    {
      if (rootNode.left == null && rootNode.right == null)
        rootNode = null;
      else if (rootNode.left != null && rootNode.right == null)
        rootNode = rootNode.left;
      else if (rootNode.left == null && rootNode.right != null)
        rootNode = rootNode.right;
      else // two children
      {
        if (rootNode.right.left == null)
        {
          rootNode.right.left = rootNode.left;
          rootNode = rootNode.right;
        }
        else
        {
          TreeNode q = rootNode.right;
          TreeNode p = rootNode.right;
          while (p.left.left != null)
            p = p.left;
          q = p.left;
          p.left = q.right;
          q.left = rootNode.left;
          q.right = rootNode.right;
          rootNode = q;
        }
      } // two children
    } // valu == rootNode.data
  } // rootNode != null
}

The recursive Height method is:

public int Height()
{
  return Height(this.root);
}

private int Height(TreeNode rootNode)
{
  if (rootNode == null)
    return 0;
  else if (rootNode.left == null && rootNode.right == null)
    return 0; // weird: but that’s the def. see Wikipedia.
  else
    return 1 + Math.Max(Height(rootNode.left), Height(rootNode.right));
}

All in all, coding up a binary search tree was a bit trickier than I remembered but it was a lot of fun.

 

This entry was posted in Software Test Automation. Bookmark the permalink.