Hierarchical Datastructure – Binary Tree Implementation

Introduction

This is the third article in the series of non-linear data structures, to read more about the previous article, please check the topic HIERARCHICAL DATA STRUCTURE – TREE ADT. People might feel that the pace with which we are progressing is too slow, but I woul dlike to assure you that these are the articles which are the roots of the non-linear data structures, if we do not spend enough time on these, we might face bigger challenegs later. To get updates on the other articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

This article will mostly focus on the concrete implementation of the binary tree data strucuture and learn all the algorithms and understand their running time calculations. This will help us build our base strong enough to deal with the general as well as the special cases of Binary Tree, for e.g. Binary Search Tree, AVL (Height Balanced Trees) etc.

A Note to the Reader : This article refers and uses plenty of concepts and declarations from the previous articles. Hence, it is a sincere request to go through the articles listed below in the same order to get the most of this:

  1. Hierarchical Datastructure – detailed discussion
  2. Hierarchical Data Structure – Tree ADT

Implementation

We already spent enough time undertanding the basics and defining the contract for the Tree ADT in general and Binary Tree in particular. Here we will try to provide the users with a concrete implementation which they can directly use as a Tree.

To begin with, we will provide the concrete implementation of our BTPosition interface to get a concrete BTNode class which implements a BTPosition. The methods for which BTNode has to provide an implementation includes methods from BTPosition interface and because the BTPosition interface extends Position interface, so we need to provide the implementaiton for the method(s) from the Position interface as well.

The methods are listed below:

Method(s) from BTPosition interface

Method(s) from Position interface

Now we can see that these methods talk about four different properties about the node p. The node p may have a left child, a right child, a parent and an element stored at p.

So, we define four properties in the BTNode implementation and also provide the implementation for all the methods listed above. We also define a constructor which will create an instance of BTNode by accepting all these four properties ( few of these properties can be null at the time of BTNode object creation).

All the get methods will just return the property value and all the set methods will set the property value for this instance of the BTNode. Apart from the methods declared above, we will also write a method to set the element at a given node, this will replace teh old element with the new element at this node and return the old element. This is a very useful feature we will require in later stage of our tutorial.

Below is a concrete implemenation of the BTNode:

Using the BTNode to create a concrete implementation of the Binary Tree interface.

You can call your Binary Tree anything you like, I would like to call mine LinkedBinaryTree. And we will be implementing each method of the BinaryTree interface and the Tree interface as we did it for the BTNode.

While having the discussion about binary tree, we talked about two implicit property an implementation must have to make few of the methods perform in O(1) constant time. The proeprties are root and size. Hence, we will declare these two properties in the LinkedBinaryTree class. Then we will provide an implementation for hte rest of the methods listed below:

Method(s) from BinaryTree interface

Method(s) from Tree interface

With the root and the size> property in hand, we can easily prove that the methods size(), root(), isEmpty() and isRoot() are just constant time operations with runnign time O(1).

When we start with a new LinkedBinaryTree then it will have root pointing to null and size equals to zero. Hence we will write the below constructor:

To implement the method size() we can simply return the value of the property size.

To implement the method root() we can simply return the value of the property root, bubt it might be null as well for a new tree which has not yet added a root, for such situation it would be a better user experience to throw an exception if the tree has a size equal to zero. Hence, the root() method throws an excetion, we must visit our Tree interface and add the throws clause to the root() method to keep it in sync.

The method now looks like

This calls for a new Exception class, i.e. EmptyTreeException, before proceeding further I would like to define the exception class as below:

You can make this class much better by adding some more features, but for the sake of simplicity lets make it as simple as possible.

Implementation of the root() method will look like the below:

To implement the method isEmpty() we can check if the size equals to zero then return true else return false.

Note: I am intentionally skipping the implementation fo the methods elements() and positions for discussion in the next article.

To implement the method replace(Position v, Object e) we validate the node to be a valid BTNode, becuase we are only interested in replacing the element at a BTNode. If the POsition passed is a valid BTNode then we cast the position into a BTNode and invoke the setElement method on it.

To implement the method isRoot(Position v) we can check v for null, if v is null throw exception else compare v with the root and return the result of the comparison.

To implement the method parent(Position v) we have to check that position v must not be the root, because root has no parent. If v happens to be the root then throw an expetion else cast the position to BTPosition and invoke the parent() method to return the parent.

To implement the method children(Position v) we can check v to be a valid BTPosition because we are interested in the children a node in the LinkedBinaryTree where all nodes are of type BTPosition. If it is not a valid BTPosition then throw an exception else prepare a list and add the left and the right child of v to the list and return the iterator over the list.

To implement the method isInternal(Position v) we can check v to be a valid BTPosition. If it is not a valid BTPosition then throw an exception else check if it has a left or a right child. If no child exist then it is not an internal node.

To implement the method isExternal(Position v) we can check if v is not an internal node return true else return false.

To implement the method hasLeft(BTPosition p) we can check if p is not null. If it happens to be null throw an exception else invoke the getLeft() method on p and if the returned value is not null we return a true else we return a false.

To implement the method hasRight(BTPosition p) we can check if p is not null. If it happens to be null throw an exception else invoke the getRight() method on p and if the returned value is not null we return a true else we return a false.

To implement the method left(BTPosition p) we can check if p has a left child, if not we must throw an exception, let us say it is named as BoundaryViolationException. If p has a left child we simply invoke the method getLeft() on p and return the value.

So let us declare the class BoundaryViolationException and add the throws clause in the method left(). This will also require adding the throws clause in the method declarations in the BinaryTree interface

The concrete implemenation of the left() method is below:

Similar is the implemenation of the right(BTPosition p) method. It would require the throws clause as well int he BinaryTree interface and the LinkedBinaryTree class.

If you cosely observe then the children(Position v) method would also require a change in the method signature because it invokes the left(BTPosition p) and the right(BTPosition p). Hence add a throws clause in all the method signatures where the above two methods are used.

Conclusion

We almost completed the Binary Tree concrete implemenation with the name LinkedBinaryTree and also learnt how to create an API and implement it. We are left with two methods of the Tree ADT and would like to implement it in the next article.

I would also request you all to keep coding the same code along witht he articles we are using here, it might improve the undertanding as well.

Hope this helps. Happy reading. Stay connected and stay Subscribed