How do I remove the leaves of a binary tree?

Question

I'm trying to remove all of the leaves. I know that leaves have no children, this is what I have so far.

 public void removeLeaves(BinaryTree n){  

    if (n.left == null && n.right == null){

        n = null;

    }

    if (n.left != null)

        removeLeaves(n.left);

    if (n.right != null)

        removeLeaves(n.right);

}

Answer 1

Instead of n = null, it should be:

if(n.parent != null)
  {
    if(n.parent.left == n)
    {
      n.parent.left = null;
    } 
    else if(n.parent.right == n)
    {
      n.parent.right == null);
    }
  }

Answer 2

n = null; won't help you, since n is just a local variable of your function. Instead, you'd need to set n.left = null; or n.right = null; on the parent.

I won't give you a complete solution, since this smells a lot like homework, but you could, for example, add a return value to your function to indicate whether the node in question is a leaf or not and take appropriate actions in the parent (after the call to removeLeaves).

Answer 3

Since Java passes references by values n = null; simply does not work. With this line n was pointing to the leaf and now points to nothing. So you aren't actually removing it from the parent, you are just rerouting a dummy local reference. For the solution do what Matthew suggested.

Answer 4

It's much easier if you break this down like this:

public void removeLeaves(BinaryTree n){
  if (n.left != null) {
    if (n.left.isLeaf()) {
      n.removeLeftChild();
    } else {
      removeLeaves(n.left);
    }
  }
  // repeat for right child
  // ...
}

isLeaf, removeLeftChild and removeRightChild should be trivial to implement.