Hello,

     I have written a C# class for BinarySearchTree <T> where T is generic type, which creates a binary serach tree, returns true/false if it is empty, gives leftsubtree, rightsubtree, prints nodes. I want to write a search method, int search (T element), which  will search the element if it already exists in the tree. For this I need to compare the element, with elements in the binary search tree. It is easy to do if elements are of specific type but for wrtiting a generic class, how do I compare two objects of type T, which is not known. 


 Basically, if I have two object object1, object2 of type T, and I a want to compare as follows:
 if (object1.CompareTo (object2) > 0) then go to right subtree
 else if ( object1.CompareTo (object2) > < 0) then go to leftsubtree
 else print object1 found.

 Any help will be highly appreciated.
 Thanks

Edited 3 Years Ago by vkvkvk

One way to do it is to make sure that the class T implements IComparable

class MyClass<T> where T : IComparable

This will work, but limits the user of the class to defining one and only one way to arrange the objects. A better way is to use the IComparer interface. Here's some extracted code from a class I wrote:

public class BinaryHeap<T> {
   ...
    IComparer<T> comparer;

    public BinaryHeap() {
        comparer = Comparer<T>.Default;
    }

    public BinaryHeap(IComparer<T> comp) {
        if (comp == null) {
            comparer = Comparer<T>.Default;
        } else {
            comparer = comp;
        }
    }

    ...

    while (node > 1 && comparer.Compare(heap[node], heap[parent]) > 0) {

If you can't figure out how to use it from what I've shown, ask :)

Comments
I think inheriting the IComparer interface is the only real option here

Dear Ketsuekime,

    Thanks for your prompt reply and also for thanks for the help.

Your code works perfectly. I tried comparing elements of type integers and strings using your code (T is int or T is string), it works fine. However, if the type T is say Student with attributes name and marks, and I want to compare on the basis of say marks, then how do I compare two objects? I mean, how do I write/implement IComparable.I included it in Student class but it does not work.
I do not understand the role of comparer in your code. I just copied it in my program.
Sorry in my delay to reply you. I was trying to reply, but everytime I tried to include the code, it
displayed the message use the code button, which I had used. Submitting message with code is a big problem here, so no code is included.
Thanks a lot again for your help.

Just to correct the credit where it's due, Momerath posted the code, not myself.

The way your comparer works needs to be decided by yourself, but generally you implement your IComparer on the class that ends up into your Generic.

So if you have BinaryHeap<Int32> you would create the IComparer on Int32. Your binary heap can pick up the IComparer code and perform the comparison. Note that you can't compare two different objects.

This article has been dead for over six months. Start a new discussion instead.