## 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:

- Hierarchical Datastructure – detailed discussion
- Hierarchical Data Structure – Tree ADT
- Hierarchical Datastructure – Binary Tree Implementation
- 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:

1 2 3 4 5 6 7 8 9 10 |
public class NonEmptyTreeException extends Exception { private static final long serialVersionUID = 2522158888106752581L; public NonEmptyTreeException() { super(); } public NonEmptyTreeException(String message) { super(message); } } |

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.

1 2 3 4 5 6 7 |
public Position addRoot(Object e) throws NonEmptyTreeException { if (!isEmpty()) throw new NonEmptyTreeException("Tree already has a root."); size = 1; root = createNode(e, null, null, null); return 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.

1 2 3 |
protected BTPosition createNode(Object element, BTPosition parent, BTPosition left, BTPosition right) { return new BTNode(element, left, right, parent); } |

##### 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.

1 2 3 4 5 6 7 8 |
public Position insertLeft(BTPosition v, Object e) throws InvalidPositionException { if (hasLeft(v)) throw new InvalidPositionException("Node already has a left child."); BTPosition t = createNode(e, v, null, null); v.setLeft(t); size++; return t; } |

Similarly we write an `insertRight`

method:

1 2 3 4 5 6 7 8 |
public Position insertRight(BTPosition v, Object e) throws InvalidPositionException { if (hasRight(v)) throw new InvalidPositionException("Node already has a right child."); BTPosition t = createNode(e, v, null, null); v.setRight(t); size++; return t; } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public void attach(BTPosition v, BinaryTree t1, BinaryTree t2) throws EmptyTreeException, InvalidPositionException, BoundaryViolationException { if (isInternal(v)) throw new InvalidPositionException("Cannot attach to internal node."); if (!t1.isEmpty()) { v.setLeft((BTPosition) t1.root()); ((BTPosition) t1.root()).setParent(v); size = size + t1.size(); } if (!t2.isEmpty()) { v.setRight((BTPosition) t2.root()); ((BTPosition) t2.root()).setParent(v); size = size + t2.size(); } } |

##### 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.

**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.

** 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.

**Subcase 2:**

Assume the tree under consideration is the below tree.

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:**

**Subcase 3:**

For this subcase consider the tree to be as below:

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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public Object remove(BTPosition v) throws InvalidPositionException, BoundaryViolationException { if (hasLeft(v) && hasRight(v)) throw new InvalidPositionException("Cannot remove node with two children."); BTPosition c; if (hasLeft(v)) c = (BTPosition) left(v); else if (hasRight(v)) c = (BTPosition) right(v); else c = null; if (isRoot(v)) { if (c != null) c.setParent(null); root = c; } else { BTPosition pD = (BTPosition) parent(v); if (hasLeft(pD) && v == left(pD)) pD.setLeft(c); else pD.setRight(c); if (c != null) c.setParent(pD); } size--; Object t = v.element(); v = null; return t; } |

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.

1 2 3 4 5 6 7 8 9 10 11 |
public static BTNode createTree() throws NonEmptyTreeException, InvalidPositionException{ LinkedBinaryTree myTree = new LinkedBinaryTree(); BTNode root = (BTNode) myTree.addRoot(50); BTNode leftChild = (BTNode) myTree.insertLeft(root, 23); BTNode rightChild = (BTNode) myTree.insertRight(root, 46); myTree.insertLeft(leftChild, 35); myTree.insertRight(leftChild, 28); myTree.insertLeft(rightChild, 12); myTree.insertRight(rightChild, 29); return root; } |

##### Fetching the inorder elements from our newly created tree

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class TreeMainClass { static LinkedBinaryTree myTree = new LinkedBinaryTree(); public static void main(String[] args) throws NonEmptyTreeException, InvalidPositionException, BoundaryViolationException { createTree(); printInorder(); } // method to create and build a tree. public static BTNode createTree() throws NonEmptyTreeException, InvalidPositionException{ BTNode root = (BTNode) myTree.addRoot(50); BTNode leftChild = (BTNode) myTree.insertLeft(root, 23); BTNode rightChild = (BTNode) myTree.insertRight(root, 46); myTree.insertLeft(leftChild, 35); myTree.insertRight(leftChild, 28); myTree.insertLeft(rightChild, 12); myTree.insertRight(rightChild, 29); return root; } public static void printInorder() throws InvalidPositionException, BoundaryViolationException{ Iterator<object width="300" height="150"> it = myTree.elements(); while(it.hasNext()) System.out.println(it.next() + " "); }} <h2>Conclusion</h2> In this article we learnt to use our defined <code>LinkedBinaryTree</code>, this tree can be used for any purpose where we require a binary tree. In the next article we will code for all the three traversals in a iterative way, we will also try to mirror a tree and many small programs here. We will also talk about LCA(The lowest common ancestor of given nodes and how to find it.Hope this helps, happy reading. Stay connected and stay Subscribed </object> |