Skip to main content
added 5 characters in body; edited tags; edited title
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Deleting a node from Binary Search Treea binary search tree

I have read about it at a few places and tried to write my own version,. I would like to get it reviewed.

Deleting a node from Binary Search Tree

I have read about it at few places and tried to write my own version, would like to get it reviewed.

Deleting a node from a binary search tree

I have read about it at a few places and tried to write my own version. I would like to get it reviewed.

shorter title
Link
svick
  • 24.3k
  • 4
  • 52
  • 89

Deleting a node from Binary Search Tree(BST)

class Node {
    private int value;
    private Node left;
    private Node right
    
    // getters and setters
}
 

public class DeleteNodeBST { 

    Node parent = null; 

    boolean deleteNodeBST(Node node, int value) {
        if (node == null) {
            return false;
        }
        if (node.getValue() == value) { 

            if ((node.getLeft() == null) && (node.getRight() == null)) {
                // leaf node
                node = null;
                return true;
        }
    }

    
         if ((node.getLeft() != null) && (node.getRight() != null)) {
                // node with two children
                node.setValue() = findMinimumAndReturnWithDelete(node.getRight()));
                return true;
        }
    }

    
         // either left child or right child
            if (node.getLeft() != null) {
                parent.setLeft() = node.getLeft());
                node = null;
                return true;
        }
    }

    
         if (node.getRight() != null) {
                parent.setRight() = node.getRight());
                node = null;
                return true;
            }
        }
        parent = node;
        if (node.getValue() > value) {
            return deleteNodeBST(node.getLeft(), value);
        } else {
            return deleteNodeBST(node.getRight(), value);
        }
    }

    int findMinimumAndReturnWithDelete(Node node) {
        if (node.getLeft() == null) {
            int v = node.getValue();
            node === null;
            return v;
        }
        return findMinimumAndReturnWithDelete(node.getLeft());
    }
}
class Node {
    private int value;
    private Node left;
    private Node right
    
    // getters and setters
}
 
class DeleteNodeBST {
    Node parent = null;
    deleteNodeBST(Node node, int value) {
        if (node == null) {
            return false;
        }
    if (node.getValue() == value) {
        if ((node.getLeft() == null) && (node.getRight() == null)) {
            // leaf node
            node = null;
            return true;
        }
        
         if ((node.getLeft() != null) && (node.getRight() != null)) {
            // node with two children
            node.setValue() = findMinimumAndReturnWithDelete(node.getRight());
            return true;
        }
        
         // either left child or right child
        if (node.getLeft() != null) {
            parent.setLeft() = node.getLeft();
            node = null;
            return true;
        }
        
         if (node.getRight() != null) {
            parent.setRight() = node.getRight();
            node = null;
            return true;
        }
    }
    parent = node;
    if (node.getValue() > value) {
        deleteNodeBST(node.getLeft(), value);
    } else {
        deleteNodeBST(node.getRight(), value);
    }
    
    int findMinimumAndReturnWithDelete(Node node) {
        if (node.getLeft() == null) {
            int v = node.getValue();
            node == null;
            return v;
        }
        findMinimumAndReturnWithDelete(node.getLeft());
    }
}
class Node {
    private int value;
    private Node left;
    private Node right
    
    // getters and setters
}

public class DeleteNodeBST { 

    Node parent = null; 

    boolean deleteNodeBST(Node node, int value) {
        if (node == null) {
            return false;
        }
        if (node.getValue() == value) { 

            if ((node.getLeft() == null) && (node.getRight() == null)) {
                // leaf node
                node = null;
                return true;
            }

            if ((node.getLeft() != null) && (node.getRight() != null)) {
                // node with two children
                node.setValue(findMinimumAndReturnWithDelete(node.getRight()));
                return true;
            }

            // either left child or right child
            if (node.getLeft() != null) {
                parent.setLeft(node.getLeft());
                node = null;
                return true;
            }

            if (node.getRight() != null) {
                parent.setRight(node.getRight());
                node = null;
                return true;
            }
        }
        parent = node;
        if (node.getValue() > value) {
            return deleteNodeBST(node.getLeft(), value);
        } else {
            return deleteNodeBST(node.getRight(), value);
        }
    }

    int findMinimumAndReturnWithDelete(Node node) {
        if (node.getLeft() == null) {
            int v = node.getValue();
            node = null;
            return v;
        }
        return findMinimumAndReturnWithDelete(node.getLeft());
    }
}
Source Link
daydreamer
  • 201
  • 1
  • 3
  • 9
Loading