JAVA Assignment 9 Parent reference for BST Redefine TreeNode

JAVA Assignment 9 (Parent reference for BST) Redefine TreeNode by adding a reference to a node’s parent, as shown below:

BST.TreeNode

#element

#left : TreeNode

#right: TreeNode

#parent: TreeNode

Implement the insert and delete methods in BST class to update the parent for each node in the tree.

Add the following new method in BST:

/** Return the node for the specific element.

* Return null if the element is not in the tree. */

private TreeNode getNode(E element)

/** Returns true if the node for the element is a lead */

private boolean isLeaf(E element)

/** Returns the path of the element from the specific element to the root in an array list */

public ArrayList getPath(E e)

Write a test program that prompts the user to enter 10 integers, adds them to the tree, deletes the first integer from the tree, and displays the paths for all leaf nodes.

Sample run

Enter 10 integers :

45 54 67 56 50 45 23 59 23 67

[50, 54, 23]

[59, 56, 67, 54, 23]

Solution

SOURCE CODE:

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package bst;

/**
*
* @author Gojkid
*/
public class TreeNode {
int element;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode() {
this.element = 0;
this.left = null;
this.right = null;
this.parent = null;
}
  
public TreeNode(int element) {
this.element = element;
this.left = null;
this.right = null;
this.parent = null;
}

public int getElement() {
return element;
}

public TreeNode getLeft() {
return left;
}

public TreeNode getParent() {
return parent;
}

public TreeNode getRight() {
return right;
}

@Override
public String toString() {
return element + \"\";
}
  
}

--------------------------------------------------------------------------------------------------------------------

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package bst;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

/**
*
* @author Gojkid
*/
public class BST {
  
TreeNode root;

public BST() {
this.root = null;
}
  

public void insert(int data)
{
TreeNode curr = root;
if(root == null)
{
root = new TreeNode(data);
return;
}
else
{
while(curr!=null)
{
if(data > curr.getElement())
{
  
if(curr.right==null)
{
curr.right = new TreeNode(data);
return;
}
curr = curr.right;
}
  
else
{
  
if(curr.left==null)
{
curr.left = new TreeNode(data);
return;
}
curr = curr.left;
}
  
}
}
}
   public void delete(int id){
       TreeNode current = root;
       boolean isLeftChild = false;
       while(current.element!=id){
           if(current.element>id){
               isLeftChild = true;
               current = current.left;
           }else{
               isLeftChild = false;
               current = current.right;
           }
           if(current ==null){
               return ;
           }
       }
       //if i am here that means we have found the node
       //Case 1: if node to be deleted has no children
       if(current.left==null && current.right==null){
           if(current==root){
               root = null;
           }
           if(isLeftChild ==true){
               current.parent.left = null;
           }else{
               current.parent.right = null;
           }
       }
       //Case 2 : if node to be deleted has only one child
       else if(current.right==null){
           if(current==root){
               root = current.left;
           }else if(isLeftChild){
               current.parent.left = current.left;
           }else{
               current.parent.right = current.left;
           }
       }
       else if(current.left==null){
           if(current==root){
               root = current.right;
           }else if(isLeftChild){
               current.parent.left = current.right;
           }else{
               current.parent.right = current.right;
           }
       }else if(current.left!=null && current.right!=null){
          
           //now we have found the minimum element in the right sub tree
           TreeNode successor = getSuccessor(current);
           if(current==root){
               root = successor;
           }else if(isLeftChild){
               current.parent.left = successor;
           }else{
               current.parent.right = successor;
           }          
           successor.left = current.left;
       }      
       return ;      
   }
  
   public TreeNode getSuccessor(TreeNode deleleNode){
       TreeNode successsor =null;
       TreeNode successsorParent =null;
       TreeNode current = deleleNode.right;
       while(current!=null){
           successsorParent = successsor;
           successsor = current;
           current = current.left;
       }
       //check if successor has the right child, it cannot have left child for sure
       // if it does have the right child, add it to the left of successorParent.
//successsorParent
       if(successsor!=deleleNode.right){
           successsorParent.left = successsor.right;
           successsor.right = deleleNode.right;
       }
       return successsor;
   }
  
  

/** Return the node for the specific element.
* Return null if the element is not in the tree. */
private TreeNode getNode(int element)
{
TreeNode curr = new TreeNode();
while(curr!=null)
{
if(element > curr.getElement())
curr = curr.right;
else if(element < curr.getElement())
curr = curr.left;
else
return curr;
}
return null;
}
/** Returns true if the node for the element is a lead */
private boolean isLeaf(int element)
{
TreeNode curr = root;
while(curr!=null)
{
if(element > curr.getElement())
curr.right = getNode(element);
else if(element < curr.getElement())
curr.left = getNode(element);
else
{
if(curr.left == null && curr.right == null)
return true;
}
}
return false;
}
/** Returns the path of the element from the specific element to the root in an array list */
public ArrayList getPath(int e)
{
ArrayList<TreeNode> arr = new ArrayList();
TreeNode curr=root;
while(curr!=null)
{
arr.add(curr);

if(e > curr.getElement())
curr = curr.right;
else if(e < curr.getElement())
curr = curr.left;
else
return arr;
}
return arr;
}

public void display(TreeNode root){
       if(root!=null){
           display(root.left);
           System.out.print(\" \" + root.element);
           display(root.right);
       }
}
  
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BST b = new BST();

System.out.print(\"Enter the numbers: \");
String str=br.readLine();
String inp[]=str.split(\" \");
for(int i=0;i<inp.length;i++)
{
int x = Integer.parseInt(inp[i]);
b.insert(x);
}
System.out.print(\"Enter the number: \");
int x=Integer.parseInt(br.readLine());   
ArrayList<TreeNode> al=b.getPath(x);
System.out.print(\"\ The required path :\");
Iterator itr=al.iterator();//getting Iterator from arraylist
while(itr.hasNext()){
System.out.print(itr.next().toString()+\" \");
}
  
}
}

OUTPUT:

Enter the numbers: 23 89 45 12 5 8 7 100 67 06 56
Enter the number: 7

The required path :23 12 5 8 7