Removing leaves from Binary Tree not being represented properly

Question

I have been working on creating a Binary Tree from scratch, not using built-in libraries. I am working on a function called "pruneLeaves". The job is to remove all leaves of the tree; nodes with no children.

When I step through the function with breakpoints, it appears to be removing the leaves and even prints out that it is indeed removing the proper nodes. However, when I display the tree in my main function afterwards, the nodes are still there!

I have tried for hours to figure this out, what am I overlooking?!

Program Output:

Num nodes = 9
Pruning.
12
Leaf removed
9
Leaf removed
4
Leaf removed
Tree after pruning..
3 4 5 6 7 8 9 11 12 

---

    // Recursive helper. Accepts BinaryNode as a parameter
private BinaryNode pruneLeaves(BinaryNode t) {

    // If we have no left child AND no right child, we are a leaf
    if ((t.left == null) && (t.right == null)) {

        //Print the element being removed.
        System.out.println (t.element);

        //Remove the element
        t = remove(t.element, t);

        if(t == null)
            System.out.println("Leaf removed");
    }
    // Else we have at least one child
    else {

        if (t.right != null) {
            pruneLeaves(t.right);
        }

        if (t.left != null) {
            pruneLeaves(t.left);
        }
    }
  //Return our leafless tree
  return t;
}

// Main recursive method, call the helper method by passing the root of the 
// tree, which calls it.
public void pruneLeaves () {
    pruneLeaves(this.getRoot());
}

BinaryNode getRoot () {
    return this.root;
}

/**
 * Internal method to remove from a subtree.
 * @param x the item to remove.
 * @param t the node that roots the tree.
 * @return the new root.
 */
private BinaryNode remove( int x, BinaryNode t )  {
success = false;
    if( t == null )
        return t;   // Item not found; do nothing

    if( x < t.element )
        t.left = remove( x, t.left );

    else if( x > t.element )
        t.right = remove( x, t.right );

    else {
        success = true;

        if( t.left != null && t.right != null )  { // Two children
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }

        else
        t = ( t.left != null ) ? t.left : t.right;
    }
    return t;
}

And my main method, calling the function:

    public static void main( String [ ] args )   {
    BST t = new BST( );

    t.insert(7);
    t.insert(6);
    t.insert(5);
    t.insert(3);
    t.insert(4);
    t.insert(8);
    t.insert(11);
    t.insert(9);
    t.insert(12);

    System.out.println();
    System.out.println ("Num nodes = " + t.countNodes());
    System.out.println ("Pruning.");

    // Remove leaves of the tree
    t.pruneLeaves();
    t.infix();
    System.out.println();
}

Answer 1

+1 for being right answer (only one I've found so far), but you forgot the null scenario for the root, and also to remove the root if the root itself has no children. Here's how I did it - I used your code and then made sure it fit all scenarios:

public void removeLeaves () {
    if (root != null) {
        removeLeaves (root);
    } else {
        return;
    }
}

private Node removeLeaves (Node node) {
    if (root.left == null && root.right == null) {
        root = null;
    } else {
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) {
                node.left = null;             
            } else {
                removeLeaves(node.left);
            }
        }
        if (node.right != null) {
            if (node.right.left == null && node.right.right == null) {
                node.right = null;      
            } else {
                removeLeaves(node.right);     
            }
        }
    }
    return node;
}

This code ensures that all nodes with no children are removed, and also eliminates the need for the isLeaf() function.

Answer 2

Using the link: Deleting Leaves From a Binary Tree

I have found the errors in my code and corrected them using the answer given in the link.

Correct Code as follows:

private BinaryNode pruneLeaves (BinaryNode p) {

    // There is a left child
    if (p.left != null)
        if (isLeaf(p.left)) //Is that child a leaf?
            p.left = null;             
        else
            pruneLeaves(p.left);      // If it is not, recursive call

    // Is there a right child
    if (p.right != null)
        if (isLeaf(p.right))
            p.right = null;            
        else
            pruneLeaves(p.right);     // Recursive call
    return p;
}

// Main recursive call, passes the root of calling tree to the helper method
public void pruneLeaves () {
    pruneLeaves (this.getRoot());
}

// Returns true if child is a leaf
boolean isLeaf (BinaryNode t) {
    if (t.left == null && t.right == null) {
        return true;
    }
    return false;
}