Simple Binary Search Tree

Question

At the moment I am learning algorithms and here I am trying to implement a simple binary search tree. I would like to know your suggestions on whether I am on the right track or not, and how this can be improved.

BinaryTree.cs

class BinaryTree 
{
    private Node root;
    private int count;

    public BinaryTree()
    {
        root = null;
        count = 0;
    }
    public bool isEmpty()
    {
        return root == null;
    }

    public void insert(int d)
    {
        if (isEmpty())
        {
            root = new Node(d);
        }
        else
        {
            root.insertData(ref root, d);
        }

        count++;
    }

    public bool search(int s)
    {
        return root.search(root, s);
    }

    public bool isLeaf()
    {
        if(!isEmpty())
        return root.isLeaf(ref root);

        return true;
    }

    public void display()
    {
        if(!isEmpty())
        root.display(root);
    }

    public int Count()
    {
        return count;
    }
}

Node.cs

class Node
{
    private int number;
    public Node rightLeaf;
    public Node leftLeaf;

    public Node(int value)
    {
        number = value;
        rightLeaf = null;
        leftLeaf = null;
    }

    public bool isLeaf(ref Node node)
    {
        return (node.rightLeaf == null && node.leftLeaf == null);

    }

    public void insertData(ref Node node, int data)
    {
        if (node == null)
        {
            node = new Node(data);

        }
        else if (node.number < data)
        {
            insertData(ref node.rightLeaf, data);
        }

        else if (node.number > data)
        {
            insertData(ref node.leftLeaf, data);
        }
    }

    public bool search(Node node, int s)
    {
        if (node == null)
            return false;

        if (node.number == s)
        {
            return true;
        }
        else if (node.number < s)
        {
           return search(node.rightLeaf, s);
        }
        else if (node.number > s)
        {
            return search(node.leftLeaf, s);
        }

        return false;
    }

    public void display(Node n)
    {
        if (n == null)
            return;

        display(n.leftLeaf);
        Console.Write(" " + n.number);
        display(n.rightLeaf);
    }

}

Program.cs

class Program
{
    static void Main(string[] args)
    {
        BinaryTree b = new BinaryTree();

        b.insert(1);
        b.insert(6);
        b.insert(2);
        b.insert(4);
        b.insert(5);
        b.insert(3);

        b.display();

        Console.ReadLine();
    }
}

Output

1 2 3 4 5 6

Answer 1

I don't quite understand why you'd use a ref here.

public void insertData(ref Node node, int data)
{
    if (node == null)
    {
        node = new Node(data);

    }
    else if (node.number < data)
    {
        insertData(ref node.rightLeaf, data);
    }

    else if (node.number > data)
    {
        insertData(ref node.leftLeaf, data);
    }
}

Why not just return the node?

public Node insertData(Node node, int data)
{
    if (node == null)
    {
        return new Node(data);

    }

    if (node.number < data)
    {
        return insertData(node.rightLeaf, data);
    }

    if (node.number > data)
    {
        return insertData(node.leftLeaf, data);
    }
}

---

Your capitalization is consistent, but slightly confusing and non-standard. For example, both your private fields and public methods are camelCase.

   public void insert(int d)
    {
        if (isEmpty())
        {
            root = new Node(d);
        }

This would be perfectly fine if you distinguished the field by using the this keyword or an underscore to make it look different from your methods.

    public void insert(int d)
    {
        if (isEmpty())
        {
            _root = new Node(d);
        }

Or

    public void insert(int d)
    {
        if (isEmpty())
        {
            this.root = new Node(d);
        }

But like I said, it's non-standard. The standard is to use PascalCase for methods, camelCase for local vars, and _underscoredCamelCase for private fields.

    public void Insert(int d)
    {
        if (IsEmpty())
        {
            _root = new Node(d);
        }

Answer 2

I can see various things that could be improved in the code, and they can be classified in the following areas:

Naming Convention

As @RubberDuck mentioned, your naming convention is a non standard one. It seems more like a "Java-world" naming. Per se, there is nothing wrong with it, just keep in mind that it will be different from the rest of the world :)

For example:

public bool search(int s)
{
    return root.search(root, s);
}

should become

public bool Search(int s)
{
    return root.search(root, s);
}

Also, try to avoid acronyms for readability's sake.

Formatting

Your formating is inconsistent. For example:

if (isEmpty())
{
    root = new Node(d);
}

and

if(!isEmpty())
root.display(root);

As can be seen, in the first example you use brackets and in the second you don't. It'd be best if you choose one format and stick to it.

In the second example there is also no indentation. In my opinion it should be something like:

if(!isEmpty())
{
    root.display(root);
}

Design

I can also see some design issues here. Just a few examples:

public int Count()
{
    return count;
}

should become:

public int Count
{
    get { return count; }
}

or better still:

public int Count { get; private set; }

as Count is a property of the tree.

Also, bool isLeaf() is not something that belongs to the tree, but to the single node, so it should be removed from the tree class.

Another design problem is represented by the void display() method. The objects should not print stuff, they should return a representation of themselves. So you should override the string ToString() method.

Yet another thing that pops up is the use of ref which should be useless in this context.

A final thing, as @Snowbody hypothesized, seems like you don't understand the practical difference between static and non static code. I'd suggest to study it further.

So, to recap, your code for the BinaryTree class should look something like this:

class BinaryTree 
{
    private Node root;

    public bool IsEmpty
    {
        get { return root == null; }
    }

    public int Count { get; private set; }

    public BinaryTree()
    {
        root = null;
        count = 0;
    }

    public void Insert(int digit)
    {
        if (IsEmpty)
        {
            root = new Node(digit);
        }
        else
        {
            root.InsertData(digit);
        }

        Count++;
    }

    public bool Search(int toSearch)
    {
        return root.search(toSearch);
    }

    public override string ToString()
    {
        string result = string.Empty;

        if(!IsEmpty)
        {
            result = root.ToString();
        }

        return result;
    }
}

And you should adapt the Node code also :)

Let me know if anything is unclear.

Answer 3

It seems that you don't understand one of the principles of object-oriented code: when you call a (non-static) method, all the fields (variables and properties) are accessible inside that method. You don't need an object reference to get at them; the object "knows" about itself. So your member functions (methods) should be rewritten:

public bool isLeaf()
{
    return (rightLeaf == null && leftLeaf == null);
}

public void insertData(int data)
{
    if (number < data)
    {
        if (rightLeaf == null)
        {
           rightLeaf = new Node(data);
        }
        else
        {
           rightLeaf.insertData(data);
        }
    }
    else if (node.number > data)
    {
        if (leftLeaf == null)
        {
           leftLeaf = new Node(data);
        }
        else
        {
           leftLeaf.insertData(data);
        }
    }
}

public bool search(int s)
{
    if (number == s)
    {
        return true;
    }
    if (number < s)
    {
       if (rightLeaf == null)
       {
           return false;
       }
       return rightLeaf.search(rightLeaf, s);
    }
    // else if (node.number > s) // only possible case
    {
       if (leftLeaf == null)
       {
           return false;
       }
       return leftLeaf.search(s);
    }

    return false;
}

public void display()
{
    if (leftLeaf != null)
    {
        display(n.leftLeaf);
    }
    Console.Write(" " + n.number);
    if (rightLeaf != null)
    {
        display(n.rightLeaf);
    }
}

Answer 4

As others have already noted the general coding convention problems i would focus on the api for improvement.

Essentially you are implementing a collection, so its important to provide collection interfaces.

The first thing i would expect is the Add method. You already have it named insert.

Another important thing is getting all the items, which is usually done with IEnumerable interface; a reasonable implementation would return items in depth first order and you already have a part of that imlemented in display method.

Its important to generalize collections to a generic version with IComparable replacing the explicit type and the comparision operators. That way your tree would work with strings for example.

Next part is the Contains and Remove methods. You already have the Contains implementation named search.

Creating a ToString displaying all the elements is not practical. I'd recommend a generic tree traverser.