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;
	}
}