Jack L. Jack L. - 3 years ago 174
Java Question

Removing All Leaves from a BinaryTree

This method is supposed to remove all leaves from a binary (no left and right branches) tree, but for some reason, it only removes one instance of a leaf from the binary tree. Why is that? I though the base case is responsible for severing the ties the parent node by setting parent.left or parent.right to null. If it isn't a leaf, it would recursively call until it hits a leaf.

Here is what I have so far:

private IntTreeNode overallRoot; // Beginning of the chain of nodes


// post: Removes All leaves from a tree
public void removeLeaves() {
if (overallRoot == null) { // If empty tree
return;
} else {
removeLeaves(overallRoot);
}

}

// helper for removeLeaves
private void removeLeaves(IntTreeNode root) {
if (root.left != null) { // tests left root
if (root.left.left == null && root.left.right == null) { // if next left node is leaf (base case)
root.left = null; // delete
} else if (root.left.left != null && root.left.right == null) { // If next right is empty
removeLeaves(root.left.left); // only check second left
} else if (root.left.right != null && root.left.left == null) { // If next left is empty
removeLeaves(root.left.right);
} else if (root.left.left != null && root.left.right != null) { // If next left/right isn't empty
removeLeaves(root.left.left);
removeLeaves(root.left.right);
}
}

if (root.right != null) {
if (root.right.left == null && root.right.right == null) { // if next left node is leaf (base case)
root.right = null; // delete
} else if (root.right.left != null && root.right.right == null) { // If next right is empty
removeLeaves(root.right.left); // only check second left
} else if (root.right.right != null && root.right.left == null) { // If next left is empty
removeLeaves(root.right.right);
} else if (root.right.left != null && root.right.right != null) { // If next left/right isn't empty
removeLeaves(root.right.left);
removeLeaves(root.right.right);
}
}
}


Here is the individual node class:

public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;

// constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}

// constructs a branch node with given data, left subtree,
// right subtree
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}

Answer Source

If in your recursive calls, instead of doing

removeLeaves(root.left.left);

you do

removeLeaves(root.left);

it should work. As Wallace points out in the comment, it looks like your're getting down two levels at a time. Also, the code could be reduced in the following way (the equivalent for the right tree)

if (root.left != null) { // tests left root
     if (root.left.left == null && root.left.right == null) { 
         root.left = null; // delete
     } else {
         removeLeaves(root.left);
     }
 }

Take into account also that this do not solve the problem of a root being itself a leave!

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download