Problem
I have implemented a BST for an assignment in C#. I am still in the process of implementing IEnumerable and ToList functions but the core of this is done.
Please review and critique this code. Additionall, I am using explicit interface implementation in order to force clients to use the interface to code against this. Is this the right way of doing it?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace DataStructures.Trees
{
public interface IBinarySearchTreeNode<T> : IComparable<IBinarySearchTreeNode<T>> where T : IComparable<T>
{
IBinarySearchTreeNode<T> Parent { get; set; }
IBinarySearchTreeNode<T> LeftChild { get; set; }
IBinarySearchTreeNode<T> RightChild { get; set; }
bool HasChildren { get; }
bool HasLeftChild { get; }
bool HasRightChild { get; }
bool IsLeftChild { get; }
bool IsRightChild { get; }
bool IsLeaf { get; }
int ChildrenCount { get; }
T Data { get; set; }
}
public interface IBinarySearchTree<T> where T : IComparable<T>
{
IBinarySearchTreeNode<T> Root { get; }
int Count { get; }
IBinarySearchTreeNode<T> AddNode(T Value);
IBinarySearchTreeNode<T> FindNode(T Value);
IBinarySearchTreeNode<T> RemoveNode(T Value);
}
public interface IPrintBinarySearchTree
{
String PrintTree();
}
public class BinarySearchTreeNode<T> : IPrintBinarySearchTree, IBinarySearchTreeNode<T> where T : IComparable<T>
{
private IBinarySearchTreeNode<T> _left;
private IBinarySearchTreeNode<T> _right;
private IBinarySearchTreeNode<T> _parent;
private T _data;
public BinarySearchTreeNode(T Value)
{
_left = _right = _parent = null;
_data = Value;
}
int IBinarySearchTreeNode<T>.ChildrenCount
{
get
{
int count = 0;
if ((this as IBinarySearchTreeNode<T>).HasLeftChild)
count++;
if ((this as IBinarySearchTreeNode<T>).HasRightChild)
count++;
return count;
}
}
T IBinarySearchTreeNode<T>.Data
{
get
{
return _data;
}
set
{
_data = value;
}
}
IBinarySearchTreeNode<T> IBinarySearchTreeNode<T>.LeftChild
{
get
{
return _left;
}
set
{
_left = value;
}
}
IBinarySearchTreeNode<T> IBinarySearchTreeNode<T>.Parent
{
get
{
return _parent;
}
set
{
_parent = value;
}
}
IBinarySearchTreeNode<T> IBinarySearchTreeNode<T>.RightChild
{
get
{
return _right;
}
set
{
_right = value;
}
}
bool IBinarySearchTreeNode<T>.HasChildren
{
get
{
return ((this as IBinarySearchTreeNode<T>).ChildrenCount > 0);
}
}
bool IBinarySearchTreeNode<T>.HasLeftChild
{
get { return _left != null; }
}
bool IBinarySearchTreeNode<T>.HasRightChild
{
get { return _right != null; }
}
bool IBinarySearchTreeNode<T>.IsLeaf
{
get { return (_left == null && _right == null); }
}
bool IBinarySearchTreeNode<T>.IsLeftChild
{
get
{
if ((_parent as IBinarySearchTreeNode<T>).LeftChild == this)
return true;
else
return false;
}
}
bool IBinarySearchTreeNode<T>.IsRightChild
{
get
{
if ((_parent as IBinarySearchTreeNode<T>).RightChild == this)
return true;
else
return false;
}
}
public int CompareTo(IBinarySearchTreeNode<T> other)
{
return this._data.CompareTo((T)other);
}
string IPrintBinarySearchTree.PrintTree()
{
return (this as IBinarySearchTree<T>).DrawTree<T>();
}
}
public class BinarySearchTree<T> : IBinarySearchTree<T> where T : IComparable<T>
{
private IBinarySearchTreeNode<T> _root;
public BinarySearchTree()
{
_root = null;
}
int IBinarySearchTree<T>.Count
{
get
{
throw new NotImplementedException();
}
}
IBinarySearchTreeNode<T> IBinarySearchTree<T>.Root
{
get
{
return _root;
}
}
/// <summary>
/// Add a node
/// </summary>
/// <param name="Value"></param>
/// <returns></returns>
IBinarySearchTreeNode<T> IBinarySearchTree<T>.AddNode(T Value)
{
IBinarySearchTreeNode<T> node = new BinarySearchTreeNode<T>(Value);
IBinarySearchTreeNode<T> parent = null;
IBinarySearchTreeNode<T> current = null;
if (_root == null)
{
_root = node;
return node;
}
current = _root;
while (current != null)
{
parent = current;
if (current.Data.CompareTo(node.Data) < 0)
current = current.RightChild;
else
current = current.LeftChild;
}
if (parent.Data.CompareTo(node.Data) <= 0)
{
parent.RightChild = node;
node.Parent = parent;
}
else
{
parent.LeftChild = node;
node.Parent = parent;
}
return node;
}
/// <summary>
/// Find a node
/// </summary>
/// <param name="Value"></param>
/// <returns></returns>
IBinarySearchTreeNode<T> IBinarySearchTree<T>.FindNode(T Value)
{
//Root itself is null
if (_root == null)
return null;
IBinarySearchTreeNode<T> current = _root;
while (current != null)
{
if (current.Data.CompareTo(Value) == 0)
break;
else if (current.Data.CompareTo(Value) > 0)
current = current.LeftChild;
else
current = current.RightChild;
}
return current;
}
/// <summary>
/// Remove a node from the Binary search tree
/// </summary>
/// <param name="Value"></param>
/// <returns></returns>
IBinarySearchTreeNode<T> IBinarySearchTree<T>.RemoveNode(T Value)
{
IBinarySearchTreeNode<T> CurrentNode = (this as IBinarySearchTree<T>).FindNode(Value);
if (CurrentNode == null)
return null;
IBinarySearchTreeNode<T> Parent = CurrentNode.Parent;
if (CurrentNode.ChildrenCount == 2) // Has both left and right children
{
IBinarySearchTreeNode<T> temp = this.FindMinNode(CurrentNode.RightChild); //find minimum in right subtree
CurrentNode.Data = temp.Data;//copy the value in the minimum to current
CurrentNode.RightChild = temp.RightChild;//delete the node with single child
}
else if (CurrentNode.HasLeftChild)//Only has left child
{
CurrentNode.Parent.LeftChild = CurrentNode.LeftChild;
CurrentNode.LeftChild.Parent = CurrentNode.Parent;
}
else if (CurrentNode.HasRightChild) //Only has right child
{
CurrentNode.Parent.RightChild = CurrentNode.RightChild;
CurrentNode.RightChild.Parent = CurrentNode.Parent;
}
else //No children
{
if (CurrentNode.Parent.LeftChild == CurrentNode)
CurrentNode.Parent.LeftChild = null;
else if (CurrentNode.Parent.RightChild == CurrentNode)
CurrentNode.Parent.RightChild = null;
}
return CurrentNode;
}
/// <summary>
/// Find the minium value below this node
/// </summary>
/// <param name="Node"></param>
/// <returns></returns>
public IBinarySearchTreeNode<T> FindMinNode(IBinarySearchTreeNode<T> Node)
{
if (Node == null)
return null;
IBinarySearchTreeNode<T> current = Node;
while (current.HasLeftChild)
current = current.LeftChild;
return current;
}
/// <summary>
/// Find the maximum value below this node
/// </summary>
/// <param name="Node"></param>
/// <returns></returns>
public IBinarySearchTreeNode<T> FindMaxNode(IBinarySearchTreeNode<T> Node)
{
if (Node == null)
return null;
IBinarySearchTreeNode<T> current = Node;
while (current.HasRightChild)
current = current.RightChild;
return current;
}
}
}
Solution
am using explicit interface implementation in order to force clients to use the interface to code against this. Is this the right way of doing it ?
That achieves the goal, but I see no reason why that’s a desirable goal to achieve. Why is it a good idea to make the clients — and the implementation itself! — code against this interface when they have a perfectly good class in hand?
public interface IBinarySearchTreeNode<T> : IComparable<IBinarySearchTreeNode<T>> where T : IComparable<T>
This doesn’t make any sense to me. A binary search tree is a thing which can be compared to another binary search tree? OK, I have this tree:
2
/
1 3
Is that bigger than or smaller than this one?
1
2
3
I can see that the values in the tree must be comparable to each other, but why must two trees be comparable?
bool HasChildren { get; }
bool HasLeftChild { get; }
bool HasRightChild { get; }
bool IsLeaf { get; }
int ChildrenCount { get; }
Most of these are redundant to each other.
You could get away with getting rid of all of these by saying: a binary search tree node may be empty, every node has two children, possibly empty. Now all you need it an “is empty” method. If IsEmpty is true then the node has no children, otherwise the node has children. All leaves are empty. And so on.
bool IsLeftChild { get; }
Why is it necessary to know this?
public interface IPrintBinarySearchTree
{
String PrintTree();
}
What is the advantage of having this interface over simply implementing ToString?
IBinarySearchTreeNode<T> IBinarySearchTreeNode<T>.LeftChild
{
get
{
return _left;
}
set
{
_left = value;
}
}
So the client can set the left node to anything they like? Who is maintaining the search tree invariant here? If the client is responsible for maintaining the search tree invariant then what value is your class adding over a much smaller, simpler binary tree class?
The interfaces you’ve come up with here are both too complicated and allow too much power to the client code. You’ve got too much abstraction. Are you going to have a half dozen different kinds of binary tree node, and a half dozen kinds of binary trees, each of which can use any kind of node? Unlikely. You’ll have one of each, and the former is an implementation detail of the latter.
Instead of focusing on unnecessary abstractions, simplify for the client. What does the client want? a binary search tree? No! The client wants an ordered set with fast search
interface IOrderedSet<T> : IEnumerable<T>
where T : IComparable<T>
{
void Insert(T t);
void Remove(T t);
bool Contains(T t);
}
What can the client do? Insert items, remove items, check for containment, and list all items. Everything else is a private detail of the implementing class, not a public interface, including the fact that the implementation behind the scenes is a binary search tree.