I am a beginner on Data Structures
Here is my code, I seem not to be able to figure out how to delete a little node.


Someone help me out please :D

Here all the methods needed to delete a node.

public void eraseTree()
{
    	root = null;
}

public boolean isThere(String element)
{
	if(isEmpty() == true)
	{
		return false;
	}
	//checks if the element is in the root
	else if(element.compareTo(root.getData()) == 0)
	{
		return true;
	}
	else
	{
		//starts going thru the overloaded method
		return isThere(root, element);
	}
}

public boolean isThere(Node module, String element)
    {
    	//checks if the module is null
    	if (module == null)
    	{
    		return false;
    	}
    	//checks if the element is equal to current module's data
    	else if(element.compareTo(module.getData()) == 0)
    	{
    		return true;
    	}
    	//checks if the element is less than the current module's data
    	else if(element.compareTo(module.getData()) < 0)
    	{
    		return isThere(module.getLeft(), element);
    	}
    	//checks if the element is greater than the current module's data
    	else if (element.compareTo(module.getData()) > 0)
    	{
    		return isThere(module.getRight(), element);
    	}
    	else
    	{
    		//if all else fails
    		//return false.
    		return false;
    	}
    }
public boolean isThere(Node module, String element)
{
    	//checks if the module is null
    	if (module == null)
    	{
    		return false;
    	}
    	//checks if the element is equal to current module's data
    	else if(element.compareTo(module.getData()) == 0)
    	{
    		return true;
    	}
    	//checks if the element is less than the current module's data
    	else if(element.compareTo(module.getData()) < 0)
    	{
    		return isThere(module.getLeft(), element);
    	}
    	//checks if the element is greater than the current module's data
    	else if (element.compareTo(module.getData()) > 0)
    	{
    		return isThere(module.getRight(), element);
    	}
    	else
    	{
    		//if all else fails
    		//return false.
    		return false;
    	}
}

public Node getLeftmost(Node module)
    {
    	//checks if the next node on the
    	//left side is null
    	if(module.getLeft() == null)
    	{
    		return module;
    	}
    	else
    	{
    		//recurrsion part
    		return getLeftmost(module.getLeft());
    	}
    }

public Node getRightmost(Node module)
    {
    	//checks if the next node on the
    	//right side is null
    	if(module.getRight() == null)
    	{
    		return module;
    	}
    	else
    	{
    		//recurrsion part
    		return getRightmost(module.getRight());
    	}
    }

public Node findParent(Node module, String element)
    {
    	//checks if the current element is smaller than
    	//the current data stored in the module
    	if (element.compareTo(module.getData()) < 0)
    	{
    		//if the data is equal to the current module's
    		//left module's data then it returns as parent.
    		if (element.compareTo(module.getLeft().getData()) == 0)
    		{
    			return module;
    		}
    		//else it will move to the left module with recurrsion
    		else
    		{
    			return findParent(module.getLeft(), element);
    		}
    	}
    	//checks if the current element is larger than
    	//the current data stored in the module
    	if(element.compareTo(module.getData()) > 0)
    	{
    		//if the data is equal to the current module's
    		//right module's data then it returns as parent.
    		if(element.compareTo(module.getRight().getData()) == 0)
    		{
    			return module;
    		}
    		//else it will move to the right module with recurrsion
    		else
    		{
    			return findParent(module.getRight(), element);
    		}
    	}
    	//if all else fails
    	//returns the module
    	return module;
    }

public boolean isLeaf(Node module)
    {
    	if(module.getLeft() == null && module.getRight() == null)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }

public Node findNode(Node module, String element)
    {
    	//checks if the element is equal to current module's data
    	if(element.compareTo(module.getData()) == 0)
    	{
    		return module;
    	}
    	//checks if the element is less than the current module's data
    	else if(element.compareTo(module.getData()) < 0)
    	{
    		return findNode(module.getLeft(), element);
    	}
    	//checks if the element is greater than the current module's data
    	else if (element.compareTo(module.getData()) > 0)
    	{
    		return findNode(module.getRight(), element);
    	}
    	else
    	{
    		//if all else fails
    		//return false.
    		return module;
    	}
    }

public boolean removeNode(String element)
    {
    	//check if the tree is empty
    	if (isEmpty() == true)
    	{
    		System.out.println("The tree is empty.");
    		return false;
    	}
    	else if(isThere(element) == true)
    	{
    		//this is for the root removal
	    	if(element.compareTo(root.getData()) == 0)
	    	{
	    		removeRoot();
	    		return true;
	    	}
	    	else
	    	{
	    		removeItem(element);
	    		return true;
	    	}
    	}
    	else
    	{
    		System.out.println("Item not in the tree.");
    		return false;
    	}
    }

private void removeRoot()
    {
    	if(isLeaf(root))
    	{
    		eraseTree();
    	}
    	else if(root.getLeft() != null)
    	{
    		Node replaceNode = getRightmost(root.getLeft());
    		Node parentNode = findParent(replaceNode, replaceNode.getData());
    		parentNode.setRight(replaceNode.getLeft());
    		replaceNode.setLeft(root.getLeft());
    		replaceNode.setRight(root.getRight());
    		root = replaceNode;
    	}
    	else
    	{
    		Node replaceNode = getLeftmost(root.getRight());
    		Node parentNode = findParent(replaceNode, replaceNode.getData());
    		parentNode.setLeft(replaceNode.getRight());
    		replaceNode.setLeft(root.getLeft());
    		replaceNode.setRight(root.getRight());
    		root = replaceNode;
    	}
    }

private void removeItem(String element)
    {
    	Node deleteNode = findNode(root, element);
    	
    	if (isLeaf(deleteNode) == true)
    	{
    		Node parentDelete = findParent(root, element);
    		
    		if(deleteNode.getData().compareTo(parentDelete.getRight().getData()) == 0)
    		{
    			parentDelete.setRight(null);
    		}
    		else
    		{
    			parentDelete.setLeft(null);
    		}
    	}
    	else
    	{
    		if(deleteNode.getLeft() != null)
    		{
    			Node replaceNode = getRightmost(deleteNode.getLeft());
    			Node parentReplaceNode = findParent(replaceNode, replaceNode.getData());
    			parentReplaceNode.setRight(replaceNode.getLeft());
    			replaceNode.setLeft(deleteNode.getLeft());
    			replaceNode.setRight(deleteNode.getRight());
    			deleteNode = replaceNode;
    		}
    		else
    		{
    			Node replaceNode = getLeftmost(deleteNode.getLeft());
    			Node parentReplaceNode = findParent(replaceNode, replaceNode.getData());
    			parentReplaceNode.setRight(replaceNode.getLeft());
    			replaceNode.setLeft(deleteNode.getLeft());
    			replaceNode.setRight(deleteNode.getRight());
    			deleteNode = replaceNode;
    		}
    	}
    }

Here is the node information

public class Node
{
	//private variables
	private String element;		//holds the name of the person
	private Node left;			//links the node to the left side of the tree
	private Node right;			//links the node to the right side fo the tree
	
	/*Constructor
     *Initiates all the variables
     *which the user passes values.
     *@param: String n is the person's name
     *		  Node l is the left node
     *		  Node r is the right node
     */
    public Node(String element, Node left, Node right)
    {
    	this.element = element;
    	this.left = left;
    	this.right = right;
    }
    
    /*
	 *Constructor
	 *Empty Set
	 *Initiates all the variable
	 *with no passing of values
	 */
    public Node()
    {
    	this.element = null;
    	this.left = null;
    	this.right = null;
    }
    
    /*Constructor
     *Initiates all the variable
     *which the user passes only
     *the data and not the nodes.
     *@param: String n is the person's name
     */
    public Node(String element)
    {
    	this.element = element;
    	this.left = null;
    	this.right = null;
    }
    
    /*setRight Method
     *sets the private right node to the right
     *node on the list.
     *@param: Node r
     */
    public void setRight(Node right)
    {
    	this.right = right;
    }
    
    /*getRight Method
     *returns the right Node on the list
     *@param: None
     *@return: Node right
     */
    public Node getRight()
    {
    	return this.right;
    }
    
    /*setLeft Method
     *sets the private left node to the left 
     *node on the list.
     *@param: Node l
     */
    public void setLeft(Node left)
    {
    	this.left = left;
    }
    
    /*getLeft Method
     *returns the left Node on the list
     *@param: None
     *@return: Node left
     */
    public Node getLeft()
    {
    	return this.left;
    }
    
    /*setData Method
     *sets the private data to the node
     *@param: String n is the data
     *		  being passed to the
     *		  method.
     */
    public void setData(String element)
    {
    	this.element = element;
    }
    
    /*getData Method
     *returns the name stored in the node
     *@param: None
     *@return: String name
     */
    public String getData()
    {
    	return this.element;
    }

I just need to walk away for a bit to think about it. Please ask if more information is needed.

Sorry, I can't read the whole code to figure out where you are having problem. Tell us briefly where and how exactly you are trying to delete the node. What you are expecting in your sample input, and what you are getting as output. If you become more specific, I will love to help you. Thanks.

This article has been dead for over six months. Start a new discussion instead.