Data structure to delete an Element in a tree

Complete java code to delete an Element in a tree

public class BinaryTree {
Node root;
class Node {
    int value;
    Node left;
    Node right;
  
     Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}
private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }
  
    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }
  
    return current;
}
public void add(int value) {
    root = addRecursive(root, value);
}
private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();
  
    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);
  
    return bt;
}
 private int findSmallestValue(Node root) {
        return root.left == null ? root.value : findSmallestValue(root.left);
    }
private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}
public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();
 
    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
  
    assertFalse(bt.containsNode(1));
}
private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }

    if (value == current.value) {
       // Case 1: no children
            if (current.left == null && current.right == null) {
                return null;
            }

            // Case 2: only 1 child
            if (current.right == null) {
                return current.left;
            }

            if (current.left == null) {
                return current.right;
            }

            // Case 3: 2 children
            int smallestValue = findSmallestValue(current.right);
            current.value = smallestValue;
            current.right = deleteRecursive(current.right, smallestValue);
            return current;
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}
public void delete(int value) {
    root = deleteRecursive(root, value);
}
public static void main(String[] args){
 BinaryTree bt=new BinaryTree();
bt.givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements();
bt.delete();
}
}

Leave a Comment