# Deleting all leaves from a binary tree

Josh Haverford
Greenhorn
Posts: 6

i am having trouble doing this - any suggestions?

Stephan van Hulst
Bartender
Posts: 6128
74
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
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
Posts: 6

I thought leaves meant there were no children ie. empty

I think i need a depth-first traversal

Stephan van Hulst
Bartender
Posts: 6128
74
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
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
Posts: 6128
74

Josh Haverford
Greenhorn
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
Sheriff
Posts: 21322
32
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
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
Posts: 6128
74
I'll start you off:

Ralph Cook
Ranch Hand
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
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
Posts: 6128
74
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
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
Posts: 6128
74
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.