Friday, September 13, 2013

delete a node from BST

 private boolean Delete(int data, Node node, Node grand, boolean isLeft) {
        if (node == null) {
            return false;
        }
        if (data < node.data) {
            return Delete(data, node.leftChild, node, true);
        } else if (data > node.data) {
            return Delete(data, node.rightChild, node, false);
        } else {
            if (node.leftChild != null && node.rightChild != null) {
                if (isLeft == true) {
                    Node temp = grand.leftChild;
                    grand.leftChild = findReplacement(node.rightChild);
                    node = grand.leftChild;
                    node.leftChild = temp.leftChild;
                    node.rightChild = temp.rightChild;
                } else {
                    Node temp = grand.rightChild;
                    grand.rightChild = findReplacement(node.rightChild);
                    node = grand.leftChild;
                    node.leftChild = temp.leftChild;
                    node.rightChild = temp.rightChild;
                }
            } else {
                if (node.leftChild == null && node.rightChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = null;
                    } else {
                        grand.rightChild = null;
                    }
                } else if (node.rightChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = node.leftChild;
                    } else {
                        grand.rightChild = node.leftChild;
                    }
                } else if (node.leftChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = node.rightChild;
                    } else {
                        grand.rightChild = node.rightChild;
                    }
                }
            }
            return true;
        }

    }

    Node findReplacement(Node node) {
        Node parent = null;
        Node result = null;
        while (node.leftChild != null) {
            parent = node;
            node = node.leftChild;
            result = node;
        }
        if (node.rightChild != null) {
            parent.leftChild = node.rightChild;
        } else {
            if (parent != null) {
                parent.leftChild = null;
            } else {
                result = node;
            }
        }
        return result;
    }

No comments:

Post a Comment