# Let's implement a Binary Search Tree, Part V

*This is the fifth post in this series*

*Let's implement a Binary Search Tree**Let's implement a Binary Search Tree, Part II**Let's implement a Binary Search Tree, Part III**Let's implement a Binary Search Tree, Part IV*

What keeps occurring to me about the BST implementation to this point, is that it looks an awful lot like a dictionary. Consider:

- We have keys.
- We have values.
- You can get values using the key.
- You can't have the same key twice.

Remarkably like a dictionary. Wouldn't it be nice if our BST implementation was an implementation detail of a IDictionary

In order for that to work, though, our key - currently, an integer - would need to be comparable. Comparison would also need to be *cheap*, so while it might be attractive to, say, use a hashing function over each key, given the number of times we're comparing things, that would be terribly effective.

The other question is, do we need the key to be comparable *by value* or *by reference*?

```
FooBar f = new FooBar() { AProperty = 123; BProperty = 321; }
FooBar f1 = new FooBar() { AProperty = 123; BProperty = 321; }
...
myBst[f] = "A Value";
myBst[f1] = "Another Value";
```

In the example above, myBst[f] and myBst[f1] point to different values, but the keys are bitwise equivalent - but not reference equivalent. They are at different addresses in memory.

But wait. Is this a problem?

Well, it turns out yes, it is. FooBar doesn't implement greater than / less than operators. The Equals operators is determining reference equivalence, but there is no concept of greater than / less than comparison on this type.

We can implement those operators easily enough:

```
public static bool operator <(FooBar firstType, FooBar otherType)
{
...
}
public static bool operator >(FooBar firstType, FooBar otherType)
{
...
}
```

But can we enforce this as a type constraint? We can't require our keys all implement a particular custom interface of our design - operators are static, and static methods can't be defined in an interface. And even if they could be, that'd be a terrible idea, because you'd have to re-implement or specialize all the existing types that *are* perfectly comparable, like Int32, because it doesn't implement our custom-special interface.

What about IComparable?

Let's see:

- It defines a CompareTo method that returns a value indicating if something is equal to, less than, or greater than.
- It's defined on all the intrinsic built in types - int, double, string, etc.

Yes. I think that'd do nicely.

Next up - updated implementation, and by popular request, a GitHub repo for our little implementation.