Sunday, December 13, 2015

Delete Node from Binary Search Tree

// Binary Search Tree full program is available here: link

    private BinarySearchTree ParentNode; //Parent Node of the node to delete


    private boolean LeftOrRightFlag; //Deleting node is Left from parent means true, else Right means false


    public void DeleteNode(int data)    {
        DeleteNode(this, data);
    }
    private void DeleteNode(BinarySearchTree T, int data)    {
        if(T==null) return;
        if(data==T.data)    {    //delete root note
            T.data=getMin(T.right).data;
            DeleteNode(T.right, T.data);
        }    else    {
            BinarySearchTree Current = findNode(T, data);
            if(Current.left==null && Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=null;
                else
                    ParentNode.right=null;
            else if(Current.left==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.right;
                else
                    ParentNode.right=Current.right;
            else if(Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.left;
                else
                    ParentNode.right=Current.left;
            else    {//Current node has both children
                Current.data=getMin(Current.right).data;
                DeleteNode(T.right, Current.data);
            }
        }
    }


    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }


    public BinarySearchTree findNode(BinarySearchTree T,int data)    {    //except root
        if(data==T.data)
            return T;
        else if(data<T.data)    {
            ParentNode=T;
            LeftOrRightFlag=true;
            return findNode(T.left, data);
        }    else    {
            ParentNode=T;
            LeftOrRightFlag=false;
            return findNode(T.right, data);
        }
    }
UA-39217154-2