How do I remove the leaves of a binary tree?
It's much easier if you break it 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.
a source to share
n = null;
won't help you, since n
- it's just a local variable of your function. Instead, you need to install n.left = null;
or n.right = null;
for the parent.
I won't give you a complete solution as it smells a lot like homework, but you can, for example, add a return value to your function to indicate whether the node in question is a leaf or not, do the appropriate steps in the parent (after the call removeLeaves
).
a source to share
Since Java passes references by values n = null;
, it just doesn't work. With this line, n pointed to the sheet and now points nothing. This way you are not actually removing it from the parent, you are just redirecting a dummy local link. For the solution, do what Matthew suggested.
a source to share
/* @author abhineet*/
public class DeleteLeafNodes {
static class Node{
int data;
Node leftNode;
Node rightNode;
Node(int value){
this.data = value;
this.leftNode = null;
this.rightNode = null;
}
}
public static void main(String[] args) {
Node root = new Node(1);
Node lNode = new Node(2);
lNode.leftNode = new Node(4);
root.leftNode = lNode;
Node rNode = new Node(3);
rNode.rightNode = new Node(5);
root.rightNode = rNode;
printTree(root);
deleteAllLeafNodes(root, null,0);
System.out.println("After deleting leaf nodes::");
printTree(root);
}
public static void deleteAllLeafNodes(Node root, Node parent, int direction){
if(root != null && root.leftNode == null && root.rightNode == null){
if(direction == 0){
parent.leftNode = null;
}else{
parent.rightNode = null;
}
}
if(root != null && (root.leftNode != null || root.rightNode != null)){
deleteAllLeafNodes(root.leftNode, root, 0);
deleteAllLeafNodes(root.rightNode, root, 1);
}
}
public static void printTree(Node root){
if(root != null){
System.out.println(root.data);
printTree(root.leftNode);
printTree(root.rightNode);
}
}
}
a source to share
Here is a simple java method to remove leaf nodes from a 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;
}
}
a source to share
This should work -
public boolean removeLeaves(Node n){
boolean isLeaf = false;
if (n.left == null && n.right == null){
return true;
//n = null;
}
if (n!=null && n.left != null){
isLeaf = removeLeaves(n.left);
if(isLeaf) n.left=null; //remove left leaf
}
if (n!=null && n.right != null){
isLeaf = removeLeaves(n.right);
if(b) n.right=null; //remove right leaf
}
return false;
}
a source to share