CODEWITHSUNDEEP
javadata-structures
Gaaki
Gaaki

Reputation: 63

How to remove node from Binary Tree (Java)

Heya I'm working on Binary tree and stuck on how to remove node from binary tree.I asked it from my instructor and did some googling but they wasn't helpful. My instructor said there is a 3 conditions to remove node from tree.

1.If node is leaf

2.If node has both child

3.If node has only one child

Here's code I wrote:

public void remove(Object theElement) {
    BinaryTreeNode currentNode = this.root;
    ArrayStack temp = new ArrayStack();
    while(currentNode != null) {
        if(currentNode.getLeftChild() == null  
               && currentNode.getRightChild() == null 
               && currentNode.getElement().equals(theElement)) {
            currentNode = null;
            break;
        }
        else if(currentNode.getLeftChild() != null
                    && currentNode.getRightChild() == null
                    && currentNode.getElement().equals(theElement)) {
            BinaryTreeNode p = currentNode;
            BinaryTreeNode c = currentNode.leftChild;
            while(c != null) {
                p = c;
                c = c.rightChild;
            }
            p.rightChild = null;
            System.out.println("Done removing node with left child");
            break;
        }
        else if(currentNode.getLeftChild() == null
                    && currentNode.getRightChild() != null
                    && currentNode.getElement().equals(theElement)) {
            BinaryTreeNode p = currentNode;
            BinaryTreeNode c = currentNode.rightChild;
            while(c != null) {
                p = c;
                c = c.rightChild;
            }
            p.rightChild = null;
            System.out.println("Done removing node with right child");
            break;
        }
        else if(currentNode.getLeftChild() != null
                    && currentNode.getRightChild() != null
                    && currentNode.getElement().equals(theElement)){
            BinaryTreeNode p = currentNode;
            BinaryTreeNode c = currentNode.rightChild;
            while(c != null) {
                p = c;
                c = c.rightChild;
            }
            p.rightChild = null;
            System.out.println("Done removing node with left and right child");
            break;
        }
        else {
            if(currentNode.getLeftChild() != null)
                temp.push(currentNode.getLeftChild());
            if(currentNode.getRightChild() != null)
                temp.push(currentNode.getRightChild());
        }
        if(!temp.empty()) {
            currentNode = (BinaryTreeNode)temp.pop();
        }
        else break;
    }
}

I could find the node that is to be removed, but can't remove it. Please help :)

Upvotes: 0

Views: 217

Answers (1)

Ironluca
Ironluca

Reputation: 3762

There are many ways to accomplish the above. Once way is to use recursion. Below is an example (not tested, just to demonstrate the concept).

package org.test.junk;

public class BTreeNode {

protected BTreeNode right;
protected BTreeNode left;

public void add(BTreeNode node, NodePosition nodePosition) {

    switch(nodePosition) {

        case left:{this.left=node;break;}
        case right:{this.right=node;break;}

    }//switch closing

}//add closing

public void remove(NodePosition nodePosition) {

    switch(nodePosition) {

        case left:{remove(left);break;}
        case right:{remove(right);break;}

    }//switch closing

}//remove closing

public void remove(BTreeNode node) {

    if(node==null)return;

    if(node.equals(right)) {

        if(this.right!=null) {

            this.right.remove(NodePosition.right);
            this.right.remove(NodePosition.left);
            this.right=null;

        }//if closing

    }//if closing
    else if(node.equals(left)) {

        if(this.left!=null) {

            this.left.remove(NodePosition.right);
            this.left.remove(NodePosition.left);
            this.left=null;

        }//if closing

    }//else if closing
    else return;

}//remove closing

public static enum NodePosition{

    right,left;

}//enum closing

}//class closing

The idea is that if a parent node is called to remove its children (either left or right) will first call the child to remove all of its children recursively, conceptually.

Upvotes: 1

Related Questions