aspose file tools*
The moose likes Java in General and the fly likes Deleting all leaves from a binary tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Deleting all leaves from a binary tree" Watch "Deleting all leaves from a binary tree" New topic
Author

Deleting all leaves from a binary tree

Josh Haverford
Greenhorn

Joined: Feb 16, 2011
Posts: 6


i am having trouble doing this - any suggestions?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3646
    
  16

You delete leaves by nulling out references to them in the parent node. So the base case in your recursion is when a child is a leaf; then you should null the reference. If a child isn't a leaf, call the delete function recursively on that child.

And welcome to JavaRanch!
Ralph Cook
Ranch Hand

Joined: May 29, 2005
Posts: 479
Josh Haverford wrote:

i am having trouble doing this - any suggestions?


I guess I'm having trouble understanding what this is supposed to do.

The expressions "test.left == null" and "test.right == null" test the left and right nodes for null, but they don't do anything to delete those nodes if they are not null. Nothing in your code deletes the children of any node.

"Delete" is a little ambiguous. Thought of one way, to delete all the leaves from a binary tree, all you have to do is delete the left and right nodes, if either exist, from the root. You're done. The tree has no references to the leaves from anywhere else, so they will either be eligible for garbage collection or they are referred to somewhere else.

If, by "delete" you mean that a delete method needs to be called on each node of the tree, then recursion is a reasonable tool to use. I would have a method that took a node as a parameter, passed the left and right nodes to itself recursively if they were not null, and then called delete on the parameter. It's a good beginning exercise in recursion, though I think doing something besides deleting the node would be easier to understand and still be a good exercise in recursion.

If you need more help, post back.

rc
Josh Haverford
Greenhorn

Joined: Feb 16, 2011
Posts: 6



so your saying that code?


I thought leaves meant there were no children ie. empty


I think i need a depth-first traversal
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3646
    
  16

Here's a tip: first make a method isLeaf(BSTNode node). This method should return whether or not the node has any children.

Also, you should rename your delete() method into something like deleteLeaves(BSTNode root), to make it more clear the method is supposed to remove all the leaves in the given tree, rather than delete the given node itself.

When you've done that, take another look at my first post. It states exactly how you can implement the deleteLeaves() method.
Ralph Cook
Ranch Hand

Joined: May 29, 2005
Posts: 479
I am sorry, I misread the intent. It said "delete all leaves", and I took that to mean "delete all nodes".

I agree that Mr. Van Hulst has provided the proper algorithm. Perhaps you could take a crack at it that way, and let us know if you run into questions.

rc
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3646
    
  16

Please, call me Stephan
Josh Haverford
Greenhorn

Joined: Feb 16, 2011
Posts: 6



How does this look? it is saying next isnt a field, is there another way i am supposed to be looking at the child node from the parent ?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18570
    
    8

I'm confused about what you expect that line of code to do:

What that does (or would do if it compiled) is this:

  • Assign null to the test.next variable
  • Call deleteLeaves(null)


  • Personally I wouldn't write that line of code, since it's rather obscure. If I wanted to do those two things I would write the appropriate two lines of code to do them. (But I suspect you don't quite want to do those two things.)
    Josh Haverford
    Greenhorn

    Joined: Feb 16, 2011
    Posts: 6
    Paul Clapham wrote:I'm confused about what you expect that line of code to do:

    What that does (or would do if it compiled) is this:

  • Assign null to the test.next variable
  • Call deleteLeaves(null)


  • Personally I wouldn't write that line of code, since it's rather obscure. If I wanted to do those two things I would write the appropriate two lines of code to do them. (But I suspect you don't quite want to do those two things.)



    Yeah, i realize what i have to do. I need to test whether a node is a leaf from its parent so that the
    reference to this leaf can be set to null, which deletes the leaf, but i dont understand the proper code to implement that. I am a first year java student. I know there are so many options out there but i feel so limited due to my lack of experience and knowledge..
    Stephan van Hulst
    Bartender

    Joined: Sep 20, 2010
    Posts: 3646
        
      16

    I'll start you off:
    Ralph Cook
    Ranch Hand

    Joined: May 29, 2005
    Posts: 479
    I think it only fair to tell him, also, that if .left is NOT a leaf, then there are leaves down below it somewhere, and you have JUST the routine to see if one of its children is a leaf...

    rc
    Josh Haverford
    Greenhorn

    Joined: Feb 16, 2011
    Posts: 6
    Stephan van Hulst wrote:I'll start you off:


    dont i need to set the right side to null as well?


    for what to put after the else statement, if it is not null i have it return and quit?
    Stephan van Hulst
    Bartender

    Joined: Sep 20, 2010
    Posts: 3646
        
      16

    Yes, you will have to repeat the process for the right leaf. Also, if the left or right node you are considering is not a leaf, it means it is a root of a subtree, which contains leaves you may want to delete.

    I might as well show you the final solution now. Let us know whether you understand it.


    [edited 10.000 times for typos, arghghgh]
    Josh Haverford
    Greenhorn

    Joined: Feb 16, 2011
    Posts: 6
    Stephan van Hulst wrote:Yes, you will have to repeat the process for the right leaf. Also, if the left or right node you are considering is not a leaf, it means it is a root of a subtree, which contains leaves you may want to delete.

    I might as well show you the final solution now. Let us know whether you understand it.


    [edited 10.000 times for typos, arghghgh]


    Let me get this right, so in the else statement, deleteLeaves(root.left, right) is just going to the next node making the one just checked its parent if the left/right has no children(meaning it is not a leaf), and then checking the child of that?

    Im getting a Null pointer exception when i call the deleteleaves method in my main
    deleteLeaves(tree.root);


    am i calling it right? how do i show that they have been deleted correctly?



    Also, this may sound like a stupid question, but is the height of this tree 5? I dont think my height code is working properly

    Stephan van Hulst
    Bartender

    Joined: Sep 20, 2010
    Posts: 3646
        
      16

    Here's an edited version to check for null.


    I can't say anything about the example "tree" you gave, because it doesn't show an obvious tree structure. However, from a very quick analysis, your code seems to be correct.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Deleting all leaves from a binary tree