8 Replies - 7454 Views - Last Post: 19 October 2011 - 07:25 PM Rate Topic: -----

#1 imu_1   User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

removing a leaf node from a tree

Posted 19 October 2011 - 08:57 AM

Hello,
I need to write a method which passes a node as a parameter and removes that node only if that node is leaf node. If its not,then it should not do anything.

So here's what I did:


            private Node<AnyType> remove( AnyType x, Node<AnyType> t) 
    { 
        if( t == null) 
          return t;       // do nothing , return the same element
 
          
		  else 
		  {
		   if(t.element == x && t.left == null && t.right == null) 
		      t.element = null; 
		    
		  
		    if(t.left != null) 
		     {        
			         System.out.println("Inside remove left");
					 return remove(x,t.left); 
			 } 
			else if(t.right !=null) 
			{ 
			  System.out.println("Inside remove right");
			return remove(x,t.right); 
		     }
		   }
	     return t;
	}

 



This method works only if the node that am tyring to delete is on the left subtree.If it on the right,then it doesnt remove it.It compiles and runs fine,it just doesnt remove the specific node if that nod eis on the right subtree and if its a leaf node. I hope my explanation is clear. I will appreciate your responses.

Is This A Good Question/Topic? 0
  • +

Replies To: removing a leaf node from a tree

#2 imu_1   User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: removing a leaf node from a tree

Posted 19 October 2011 - 09:08 AM

I apologize, I was getting errors every time I submitted the thread. That's why there are bunch of them. I will appreciate your responses.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12399
  • View blog
  • Posts: 45,538
  • Joined: 27-December 08

Re: removing a leaf node from a tree

Posted 19 October 2011 - 09:40 AM

Rather than just setting the element to null, let's actually remove the Node. It's easier if you work with the parent Node than the current Node. So:
-If the root is to be removed, choose a new replacement Node (generally the far-right leaf on the left side, or the far-left leaf on the right side)
-Otherwise, if the left child Node is a leaf with the matching value, set parent.left = null
-Repeat for parent.right
-Recurse for non-null children

Also, don't compare Objects using the == operator. Use the equals() method instead so you aren't comparing memory locations!
Was This Post Helpful? 0
  • +
  • -

#4 imu_1   User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: removing a leaf node from a tree

Posted 19 October 2011 - 10:49 AM

macos, i am not supposed to remove a root node. I can only remove leaf nodes if the node I am looking for to remove is leaf node. If it not,then I should not remove. You also told me to use equals method.Is equals method applicable for generic types ?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12399
  • View blog
  • Posts: 45,538
  • Joined: 27-December 08

Re: removing a leaf node from a tree

Posted 19 October 2011 - 12:19 PM

What if the root Node is the only Node present? If it satisfies the leaf property, why not remove it?

Quote

Is equals method applicable for generic types ?

Yes- all generic types are Objects.
Was This Post Helpful? 0
  • +
  • -

#6 imu_1   User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: removing a leaf node from a tree

Posted 19 October 2011 - 04:00 PM

if the root is to be removed, then it means its the only node in the tree. So we dont need to find the far right and the far left. Are you getting my point ? Am trying to remove leaf nodes.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12399
  • View blog
  • Posts: 45,538
  • Joined: 27-December 08

Re: removing a leaf node from a tree

Posted 19 October 2011 - 07:01 PM

Quote

if the root is to be removed, then it means its the only node in the tree. So we dont need to find the far right and the far left.

Very true! My mistake. Sorry about that. I was thinking for standard binary tree removals. If the root is the only Node, you can just set it to null. :)
Was This Post Helpful? 0
  • +
  • -

#8 imu_1   User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: removing a leaf node from a tree

Posted 19 October 2011 - 07:21 PM

so then how shld i go about doing it now ?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12399
  • View blog
  • Posts: 45,538
  • Joined: 27-December 08

Re: removing a leaf node from a tree

Posted 19 October 2011 - 07:25 PM

That doesn't change my logic a ton really. Just don't replace the root Node if you end up removing it. Just think about how you'd remove a tail Node from a non-circular Linked List.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1