In this post, We will learn How to perform delete operation in a binary search tree?
The Delete Operation in BST:
•First of all, We have to find the node we wish to delete (if it is there).
• If we find that the node is a leaf then delete it.
• If we find that the node has exactly one child, delete the node by making its parent refer to that child directly.
• If we find that the node has two children, replace the value in the node by the value in its successor and then after deleting the successor.
Complete Souce code:
BinaryTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
package com.kkjavatutorials.tree; /** * @author KK JavaTutorials *Binary Tree Implementation */ public class BinaryTree<E extends Comparable<? super E>> { //Root of Binary Tree private Node<E> root; /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for preOrder Processing * in BST * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Insert operation in binary search tree * @param data to insert */ public void insert(E data) { root = insert(root, data); } private static <T extends Comparable<? super T>> Node<T> insert(Node<T> node, T data) { if (node == null) { node = new Node<T>(data); } else if (data.compareTo(node.data) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = insert(node.right, data); } return node; } /** * Delete value from Binary Search Tree, if it is there * @param value has to delete from Binary Seach tree */ public void delete(E value) { root = delete(root, value); } /**Delete value from the tree rooted at node (if there) * and return the root of the resulting tree. * @param node * @param value has to delete * @return */ private static <T extends Comparable<? super T>> Node<T> delete(Node<T> node, T value) { if (node == null) { // value not in tree do nothing. } else if (value.compareTo(node.data) < 0) { node.left = delete(node.left, value); } else if (value.compareTo(node.data) > 0) { node.right = delete(node.right, value); } else { // Found it now delete it. if (node.right == null) { // node has at most one child, on the left. node = node.left; } else { // node has a right child. Replace t’s value // with its successor value. T successor = min(node.right); node.data = successor; // Delete that successor. node.right = delete(node.right, successor); } } return node; } /** * Return the minimum value in tree. * @param value minimum value in tree * @return */ private static <T extends Comparable<? super T>> T min(Node<T> value) { // To find the min, go left as far as possible. if (value.left == null) { return value.data; } else { return min(value.left); } } public Node<E> getRoot() { return root; } } |
ClientTest.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
package com.kkjavatutorials.client; import java.util.Scanner; import com.kkjavatutorials.tree.BinaryTree; /** * Client Program to test insert operation in Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); binaryTree.insert(10); binaryTree.insert(15); binaryTree.insert(5); binaryTree.insert(40); binaryTree.insert(80); binaryTree.insert(60); binaryTree.insert(70); System.out.println("Original Binary tree..."); //Call for preOrder processing binaryTree.preOrder(binaryTree.getRoot()); System.out.println(); System.out.println(); Scanner scanner = null; try { System.out.println("Enter Value which you want to delete:"); scanner = new Scanner(System.in); int deleteNodeValue = scanner.nextInt(); binaryTree.delete(deleteNodeValue); System.out.println("After deleting node with value:"+deleteNodeValue +" Binary tree.."); //Call for preOrder processing binaryTree.preOrder(binaryTree.getRoot()); } catch (Exception e) { e.printStackTrace(); }finally { if(scanner != null) scanner.close(); } } } |
The Input/output of This Program:
Original Binary tree…
10 5 15 40 80 60 70
Enter Value which you want to delete:
40
After deleting node with value:40 Binary tree..
10 5 15 60 80 70
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
That’s all about Delete operation in a binary search tree?
If you have any feedback or suggestion please feel free to drop in below comment box.