Hierarchical Datastructure – Adding and Deleting Nodes

Introduction

This is the fifth article in the series of non-linear data structures, to read more about the previous article, please check the topic Hierarchical Datastructure – Tree Traversals. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

Now that we have done a lot of base building and hard work, I decide to keep this an easy one for the readers. Also, we are not left with many concepts, they are already covered in the articles listed below:

  1. Hierarchical Datastructure – detailed discussion
  2. Hierarchical Data Structure – Tree ADT
  3. Hierarchical Datastructure – Binary Tree Implementation
  4. Hierarchical Datastructure – Tree Traversals

Note for the readers : If you have not followed till now and want a quick start, then please download the zip code, which contains all the necessary files to move ahead from this point.
Code tree.zip
We learn here about Adding and Deleting Nodes in the binary tree.

Now we will try to use our completed Tree implementation the Linked Binary Tree. First of all we will try and create a tree, then add some children and try to print the traversals.

Creating a tree using the LinkedBinaryTree class.

Adding the root to the tree

To create a tree we need to add a root to the tree, point worth noting is that the tree must be empty before we attempt to add a root, hence the method must contain a throws clause to throw the NonEmptyTreeException. Just defining another basic exception class below:

To add the root, we create a node and assign it to the root property of our tree, also we increase the size property to 1 and return the reference to the root.

Add the above method to our LinkedBinaryTree class. The createNode method is a helper method which instantiates a BTNode and returns the reference. Let us say we are trying to create a Node N, then the method accepts an element e to stored at the node N, it also accepts a node reference P which has to be the parent of the node N, a left child node reference L and a right child node reference R. We may choose to pass most of the details as null, but passing an element makes sense.

Adding left and right children to the tree

After adding a root we must add some more nodes, we start with adding a left and a right child one at a time to the root node. We write a method insertLeft which accepts a BTPosition v (at which we have to insert a left child) and an element e (which is the value stored at the left child).

Condition: We need to check if the BTPosition v doesn’t have a left child, in case it already has a left child, just throw an exception with appropriate message. If there is no left child, create a node with e as element and v as parent, leave its left and right to null. After that we also need to set the new node (t) as v’s left, increase the size of the tree by 1 and return the newly created node t.

Similarly we write an insertRight method:

What if we want to attach a left and a right child at the same time? Or what if we want to attach a left and a right subtree to a node? It is as simple as inserting a left and a right child simultaneously. It’s just that we cant attach any node or subtree to an internal node. Hence we throw an exception if the node where we trying to attach is an internal node.

Removing a node from a Tree

This might be a bit tricky, let us try to keep it simple.

Case 1:
If the node to be deleted i.e. v has left and right child, we cannot remove the node. So throw an exception with appropriate message. This would be similar to the below diagram.
tree5
Case 2:
If the node v just has a left child store the left child in a temporary node c or if v has a right child store the right child in the temporary node c. This would be simlar to the diagram below and we will store L in the temporary node c.
tree6
Subcase 1:
Check if v(the node to be removed) is the root and c has a value, then set c’s parent to null and make c as the root of the tree. This would be similar to the below diagram.
lorr
Subcase 2:
Assume the tree under consideration is the below tree.
subcase2-part1
According to the first statement we store LCL in the temporary node c. If v is not the root, then store v’s parent to a temporary node pD, so we store X into pD.
If pD has left child and v is the left child of pD then set c as the left child of pD because we are about to remove v. Hence, we set node containing LCL as the left child of X.

The tree would like like below:
subcase2-part2

Subcase 3:
For this subcase consider the tree to be as below:
subcase3-part1

According to the first statement we store LCR in the temporary node c. If v is not the root, then store v’s parent to a temporary node pD, so we store X into pD.
If pD doesn’t have left child or v is not the left child of pD then set c as the right child of pD . Hence, we set node containing LCR as the right child of X.

The tree looks as below:

subcase3-part2

And we are done, just add all this method to our LinkedBinaryTree implementation.

Below is the code to add a root, a left and a right child. We will also add two nodes to the left child and two nodes to the right child.

Fetching the inorder elements from our newly created tree

Just invoke the elements() method on the tree, which we defined in the last article.