Binary Trees are tree type data structures that contain two child nodes. They can be used to implement Binary Search trees, structures where the left child has a value lesser than the node and the right child has a greater value. Usually Linear collection objects require iteration linearly over the list. In the worst case scenario that the element to be searched is at the end of the list this can take a really really long time. For Binary Trees the search time is cut by half. Since every node tells the search which direction to go and search.
I implemented a basic Binary Tree in .NET for adding custom types. The Tree is generic and can be used to add any type objects. Also the object must implement the generic versions of IComparable and IEquitable for their types and object types. This leaves the search logic’s implementation to the type rather than the data structure. The complete solution can be downloaded here.
Lets see the declaration of the Binary Tree along with the private members.
class BinaryTree<T> where T:IComparable<T>, IEquatable<T>, IEquatable<object>, IComparable<object> { BinaryTree<T> _parentNode; BinaryTree<T> _leftNode; BinaryTree<T> _rightNode; public T Value { get; set; }
Each BinaryTree object must be aware of its parent node and its left and right children, and the value it holds. Lets see the logic for adding the node. The adding logic is recursive. If it finds a null value, then the value is substituted. If not, then the node to be added is compared. If the value is lesser than the same method is called on the leftnode. This happens recursively till we get the node where the value is to be added.
public void AddNode(T _nodeTobeAdded) { if (null==Value) //We found the value. Yay!! this.Value = _nodeTobeAdded; else { //Compare the node to be added. Here the //type's IComparable is called. if (_nodeTobeAdded.CompareTo(Value) < 0) { //Go down the left node. If the left node is null, //then create a new object, else return the existing object. _leftNode = null==_leftNode ?new BinaryTree<T>(this):_leftNode; _leftNode.AddNode(_nodeTobeAdded); } else { //Go Down the right node. _rightNode = null==_rightNode?new BinaryTree<T>(this):_rightNode; _rightNode.AddNode(_nodeTobeAdded); } } }
The GetNode method follows a similar logic, with recursive searching of the tree till a match is found, if no match is found then a null value is returned. Note that only around half of the tree is searched, rather than all of the nodes, as would be the case with a linkedList. GetNode is implemented both for the type and an object. In both cases the Equals method’s implementation is called, giving the generic type the ability to decide on its own equality logic.
public T GetNode(T _nodeToBeGotten) { if(_nodeToBeGotten.Equals(Value)) return Value; else if(_nodeToBeGotten.CompareTo(Value)<0) return null==_leftNode? default(T): _leftNode.GetNode(_nodeToBeGotten); else return null==_rightNode?default(T): _rightNode.GetNode(_nodeToBeGotten); } public T GetNode(object o) { if (Value.Equals(o)) return Value; else if (Value.CompareTo(o)>0) return (null == _leftNode) ? default(T) : _leftNode.GetNode(o); else return null == _rightNode ? default(T) : _rightNode.GetNode(o); }
Deleting is a bit tricky business. We have four scenarios here:-
- Its a leaf node, i.e. both the left and right children are null. This is the simplest scenario. Simply set the node itself to null
- The LeftNode is null but the right node is not, in this scenario – the node’s right node is set to the parent node’s right node, and the node is set to null.
- The Right node is null but left node is not. It is handled similar to the previous scenario.
- Both leftNode and rightNode is not null. In this scenarios we need to go down the leftnode, and iterate to its right most non empty node. This node is to be replaced with the node to be deleted. Just the value needs to be replaced and the right most node should be orphaned.
public void DeleteNode(object o) { BinaryTree<T> _tempNode1 = this.GetTreeNode(o); DeleteNode(_tempNode1); } public void DeleteNode(T _nodeTobeDeleted) { BinaryTree<T> _tempNode1 = this.GetTreeNode(_nodeTobeDeleted); DeleteNode(_tempNode1); } private void DeleteNode(BinaryTree<T> _tempNode1) { BinaryTree<T> _tempNode2 = _tempNode1; if ((null == _tempNode1._leftNode) && (null == _tempNode1._rightNode)) _tempNode1._parentNode = null; else if (null == _tempNode1._leftNode) _tempNode1._parentNode._rightNode = _tempNode1._rightNode; else if (null == _tempNode1._rightNode) _tempNode1._parentNode._leftNode = _tempNode1._leftNode; else { bool _goingRight = false; _tempNode1 = _tempNode1._leftNode; while (_tempNode1._rightNode != null) { _tempNode1 = _tempNode1._rightNode; _goingRight = true; } _tempNode2.Value = _tempNode1.Value; if (_goingRight) _tempNode1._parentNode._rightNode = null; else _tempNode1._parentNode._leftNode = null; _tempNode1 = null; } } //Private methods to get the nodes to be deleted private BinaryTree<T> GetTreeNode(T _nodeToBeGotten) { if (_nodeToBeGotten.Equals(Value)) return this; else if (_nodeToBeGotten.CompareTo(Value) < 0) return null == _leftNode ? default(BinaryTree<T>) : _leftNode.GetTreeNode(_nodeToBeGotten); else return null == _rightNode ? default(BinaryTree<T>) : _rightNode.GetTreeNode(_nodeToBeGotten); } private BinaryTree<T> GetTreeNode(object o) { if (Value.Equals(o)) return this; else if (Value.CompareTo(o) > 0) return (null == _leftNode) ? default(BinaryTree<T>) : _leftNode.GetTreeNode(o); else return null == _rightNode ? default(BinaryTree<T>) : _rightNode.GetTreeNode(o); }
The class which could be added to the tree needs to implement the four interfaces i mentioned. I implemented an Employee class which has just two fields Name and age and the comparison is done based on the age.
class Employee : IComparable<Employee>,IEquatable<Employee>,IEquatable<object>,IComparable<object> { private string _name; private int _age; public int Age{get{return _age;}} public Employee(string _name, int _age) { this._name = _name; this._age = _age; } #region IComparable<Employee> Members public int CompareTo(Employee other) { if (this._age < other._age) return -1; else return 1; } #endregion public bool Equals(Employee other) { if (this._age == other._age) return true; else return false; } #region IEquatable<object> Members public override bool Equals(object other) { int _age=0; if (int.TryParse(other.ToString(), out _age)) { return this._age == _age ? true : false; } else return false; } #endregion #region IComparable<object> Members public int CompareTo(object other) { int _age = 0; if (int.TryParse(other.ToString(), out _age)) return this._age < _age ? -1 : 1; else return 1; } #endregion }
This is the main method which adds a few objects to the tree collection.
static void Main(string[] args) { BinaryTree<Employee> _btree = new BinaryTree<Employee>(new Employee("RootValue",40)); _btree.AddNode(new Employee("Test1", 34)); _btree.AddNode(new Employee("Test2", 26)); _btree.AddNode(new Employee("Test3", 65)); }