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);

}

Solution 1

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.

Solution 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).

Solution 3

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);
    }
  }

Solution 4

Here's a simple java method to delete leaf nodes from binary tree

public BinaryTreeNode removeLeafNode(BinaryTreeNode root) {
    if (root == null)
        return null;
    else {
        if (root.getLeft() == null && root.getRight() == null) {     //if both left and right child are null
            root = null;                                             //delete it (by assigning null)
        } else {
            root.setLeft(removeLeafNode(root.getLeft()));            //set new left node 
            root.setRight(removeLeafNode(root.getRight()));          //set new right node   
        }
        return root;
    }

}

Solution 5

Easy method with recusrion .

 public static Node removeLeaves(Node root){
          if (root == null) { 
            return null; 
        } 
        if (root.left == null && root.right == null) { 
            return null; 
        } 

        root.left = removeLeaves(root.left); 
        root.right = removeLeaves(root.right); 

        return root;
  }

View more solutions

Comments

[Can Sahin]

This will fail with a NullPointerException if the root is a leaf itself.

[flopex]

What I'm doing is a data structure, meaning that I built the BinaryTree class and in this case the parent would be n.

[Scratte]

Please add some explanation to how this works. I don't see how it removes the leaves of the tree provided.

[Aman Thakur]

Basically we're doing this recursively, so we are calling on left and right node from root node having faith that child will remove its leaf node. Now recall the property of leaf node that is it has null in both right and left node. we're checking that, if it is so, then we're returning null from that node means that node is now returned as null.

[Scratte]

My mistake. I see it now root.left = removeLeaves(root.left) is an assignment :)