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