# Simple Binary Search Tree

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

}
}


Output

1 2 3 4 5 6

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


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.

• This is helpful, but can you please tel me how can I call ToString() method to display items in the tree. Thanks. – Programm-ist Jun 4 '15 at 14:31
• There are various ways to build a string representation of a tree. One way could be to just build strings like [item;parent;level] for each node and concatenate them in order to get the final string. Another way would be to build a line composed of "\t"s and the item for each node. It's up to you how you want to represent the tree via a string. I'd suggest to decide how you want to represent the tree and if you want help in building the function I'd suggest to ask in StackOverflow. – Gentian Kasa Jun 5 '15 at 12:40
• Am I to then understand that it is ok to not use brackets on (assuming its appropriate) as long as you do it consistently throughout? – DaImTo Oct 20 '16 at 5:38
• @DaImTo, basically yes (given that everything works as it should). At the end of the day it's just a matter of personal taste. If it's ok or not depends also on various factors. This SO post contains some useful insights on the topic. – Gentian Kasa Oct 20 '16 at 7:55

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

• Of course, Python's implementation of OO uses the first parameter, traditionally named self, and all the code must refer to that variable to get at the members. – Snowbody Mar 30 '16 at 23:21

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.