You just have basic knowledge about Binary Search Tree (BST). Now, it’s time to study about delete a node in Binary Search Tree. It is quite different from operations like searching and insertion a node in BST.
Delete a node in Binary Search Tree
There are three cases since doing deletion of a node in Binary Search Tree:
Node to be deleted is leaf
First, you need to search that node then make it null. It is the simplest deletion.
Node to be deleted has only one child
If node have one children then you need to find that deleted node and connect parent of deleted node directly to child of the deleted node.
Node to be deleted has two children
If it has two nodes, we need to connect parent of node to the leftmost node(it is also minimum node) of right subtree or rightmost node(it is also maximum node) of left subtree.
Here it is replacing node 20 with node 30. Node 30 is minimum element in right subtree of 20 and deleting node 30.
A complete implementation in Java.
Here is a complete program demonstrate three cases we can delete a node in Binary Search Tree.
|
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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
// Node binary tree class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } // A program to demonstrate search and insert operation class SimpleBST { Node root; SimpleBST() { root = null; } //searching a given data in Binary Search Tree public Node searchNode(Node root, int data) { // tree is empty or root node contains a given data if (root==null || root.data==data) return root; // a given data is less than root's data if (root.data > data) return searchNode(root.left, data); // a given data is greater than root's data return searchNode(root.right, data); } /* A recursive method to insert a new data in BST */ Node insertNode(Node root, int data) { // If the tree is empty, create a new node if (root == null) { root = new Node(data); return root; } // If not, recur down the tree if (data < root.data) root.left = insertNode(root.left, data); else if (data > root.data) root.right = insertNode(root.right, data); return root; } /* A recursive function to insert a new key in BST */ Node deleteNode(Node root, int data) { /* Tree is empty */ if (root == null) return root; /* Recur down the lef subtree or right subtree */ if (data < root.data) root.left = deleteNode(root.left, data); else if (data > root.data){ root.right = deleteNode(root.right, data); } // if a given data is equal to root's data else { // node with only one child or no child if (root.left == null){ return root.right; }else if (root.right == null){ return root.left; } // Node with two children // Finding minimum node from right subtree Node minNode = searchMinNode(root.right); // Replacing root node (current node) with minimum node from right subtree root.data = minNode.data; // Deleting minimum node from right now deleteNode(root.right, minNode.data); } return root; } // Search min data of a node Node searchMinNode(Node root) { while (root.left != null) { root = root.left; } Node minNode = root; return minNode; } /* Visit its nodes in inorder - (left,root,right)*/ void visitInorder(Node node) { if (node == null) return; //1. First recur on left child visitInorder(node.left); //2. Print the left current node System.out.print(node.data + " "); //3. Recur on right child visitInorder(node.right); } // Main method public static void main(String[] args) { SimpleBST tree = new SimpleBST(); tree.root = tree.insertNode(tree.root,60); tree.root = tree.insertNode(tree.root,20); tree.root = tree.insertNode(tree.root,10); tree.root = tree.insertNode(tree.root,40); tree.root = tree.insertNode(tree.root,70); tree.root = tree.insertNode(tree.root,60); tree.root = tree.insertNode(tree.root,80); tree.root = tree.insertNode(tree.root,30); // print inorder traversal of the BST tree.visitInorder(tree.root); //search a node Node node = tree.searchNode(tree.root, 70); System.out.println("\nSearch result is: "+node.data); //Node to be deleted has two children tree.deleteNode(tree.root,20); System.out.println("after deleting node 20"); tree.visitInorder(tree.root); //Node to be deleted has one children tree.deleteNode(tree.root,70); System.out.println("\nafter deleting node 70"); tree.visitInorder(tree.root); //Node to be deleted is leaf tree.deleteNode(tree.root,80); System.out.println("\nafter deleting node 80"); tree.visitInorder(tree.root); } } |
Here is output of the above program
Time Complexity
In worst case, you have to travel from root to the deepest leaf node. So time complexity of delete operation is O(h) where h is height of Binary Search Tree.
That’s all about Delete a node in Binary Search Tree tutorial.
