TORONTO KIDS COMPUTER CLUB | PMCA Sunday 12:00 Java Homework 20.05.03.
17470

# PMCA Sunday 12:00 Java Homework 20.05.03.

## 08 May PMCA Sunday 12:00 Java Homework 20.05.03.

Continue with the code in the previous class. Write a method to find the depth of the given tree, for example:

The depth of the above tree is 4 as the last leaf node with value 16 is at level 4 of the tree.

Please find the  code below:

`Driver.java`
```import java.util.Arrays;
import java.util.Scanner;

public class Driver {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner takeInput=new Scanner(System.in);

Tree t=new Tree();
System.out.println("Write negative number to exit. "
+ "write a positive number to add to node");

while(true) {
int number=takeInput.nextInt();
if(number<=0) {
System.out.println("Exiting and printing the node");
break;
}
Node n=new Node(number);
t.insertToBinarySearchTree(n);
}

t.printTree(1);
//		System.out.println("Before p"+t.parentNode.number);
t.deleteNode(17);
//		System.out.println("Before p"+t.parentNode.number);
t.printTree(1);
}

}

```
```Tree.java
```
```public class Tree {
Node parentNode=null;

/*
* Method to print  the tree
* if the type is 1 than it will do preordertraversal
* if type is 2 than it will do postordertraveral
* if type is 3 than it will do inorderTraversal
* */
public void printTree(int type) {
if(type==1) {
preOrderTraversal(parentNode);
}
else if(type==2) {
postOrderTraversal(parentNode);
}
else {
inorderTraversal(parentNode);
}
}
public void preOrderTraversal(Node currentNode) {
if(currentNode==null) {
return;
}
System.out.println(currentNode.number);

preOrderTraversal(currentNode.LeftChild);
preOrderTraversal(currentNode.RightChild);

}
// copy it
public void postOrderTraversal(Node currentNode) {
if(currentNode==null) {
return;
}
postOrderTraversal(currentNode.LeftChild);
postOrderTraversal(currentNode.RightChild);
System.out.println(currentNode.number);

}

public void inorderTraversal(Node currentNode) {
if(currentNode==null) {
return;
}
inorderTraversal(currentNode.LeftChild);
System.out.println(currentNode.number);
inorderTraversal(currentNode.RightChild);

}

// driver function to insertToBinarySearchTree
public void insertToBinarySearchTree(Node node) {
if(parentNode==null) {
parentNode=node;
}
else {
insertNode(node,parentNode);
}
}

// code to insertNode to the tree
private void insertNode(Node node,Node currentNode) {

if(currentNode.number<node.number ) {
if(currentNode.RightChild==null) {
node.Parent=currentNode;
currentNode.RightChild=node;
return;
}
else {
insertNode(node, currentNode.RightChild);
}
}
else {

if(currentNode.LeftChild==null) {
node.Parent=currentNode;
currentNode.LeftChild=node;
return ;
}
else {
insertNode(node,currentNode.LeftChild);
}
}
}

public  Node findNode(int number,Node currentNode) {
if(currentNode==null) {
return null;
}
if (currentNode.number==number) {
return currentNode;
}
else if(currentNode.number>number) {
return findNode(number,currentNode.LeftChild);
}
else {
return findNode(number,currentNode.RightChild);
}
}

// write the code to delete a node from Binary search tree

public  boolean deleteNode(int number) {
//find the node with the number and delete the node
//write the code here
Node to_delete=findNode(number,parentNode);
String side=null;

System.out.println(to_delete);
if(to_delete==null) {
return true;
}
if(to_delete.Parent.LeftChild==to_delete) {
side="left";
}
else {
side="right";
}
// if to_delete is leaf
if(to_delete.RightChild==null && to_delete.LeftChild==null) {

if(to_delete.Parent.LeftChild!=null && to_delete.Parent.LeftChild==to_delete) {
to_delete.Parent.LeftChild=null;
}
if(to_delete.Parent.RightChild!=null && to_delete.Parent.RightChild==to_delete) {
to_delete.Parent.RightChild=null;
}
}

// if to_delete is not a leaf node
if(to_delete.RightChild!=null && to_delete.RightChild.LeftChild!=null) {
Node leftmostChild=findLeftMostChild(to_delete.RightChild);
System.out.println("A"+leftmostChild.number);
replaceNode(to_delete, leftmostChild);
}
else if(to_delete.LeftChild!=null && to_delete.LeftChild.RightChild!=null) {
Node rightmostChild=findRightMostChild(to_delete.LeftChild);

System.out.println("B"+rightmostChild.number);
replaceNode(to_delete,rightmostChild);
}
else {

if(to_delete.RightChild!=null) {
if(side=="right") {
to_delete.Parent.RightChild=to_delete.RightChild;
to_delete.RightChild.Parent=to_delete.Parent;
to_delete.RightChild.LeftChild=to_delete.LeftChild;
}
else {
to_delete.Parent.LeftChild=to_delete.RightChild;
to_delete.RightChild.Parent=to_delete.Parent;
to_delete.LeftChild.Parent=to_delete.RightChild;
to_delete.RightChild.LeftChild=to_delete.LeftChild;
}
}

else {

}
}

return false;
}

public void replaceNode(Node toReplace,Node toReplaceWith) {
deleteNode(toReplaceWith.number);
toReplace.number=toReplaceWith.number;

}

public Node findRightMostChild(Node currentNode) {

if(currentNode==null) {
return null;
}

if(currentNode.RightChild==null) {
return currentNode;
}

return findRightMostChild(currentNode.RightChild);
}

public Node findLeftMostChild(Node currentNode) {

if(currentNode.LeftChild==null) {
return currentNode;
}
return findLeftMostChild(currentNode.LeftChild);
}
}

```
`Node.java`
```public class Node {

int number;
Node LeftChild;
Node RightChild;
Node Parent;
public Node(int number) {
this.number=number;
}
}
```