Deletion from a binary search tree

Deletion from a binary search tree. Made by : p Gaurav Kumar Naidu (F_35) Aniket Nayak (F_12).

Properties of binary search tree. The left subtree of a node contains only nodes with keys lesser than th nodes key. The right subtree of a node contains only nodes wih keys greater than the nodes key. The left and right subtree each must also be a binary search tree..

6. 2. 8. 1. 4. 3.

Properties of binary search tree. The left subtree of a node contains only nodes with keys lesser than th nodes key. The right subtree of a node contains only nodes wih keys greater than the nodes key. The left and right subtree each must also be a binary search tree..

6. 2. 8. 1. 4. 3.

Properties of binary search tree. The left subtree of a node contains only nodes with keys lesser than th nodes key. The right subtree of a node contains only nodes wih keys greater than the nodes key. The left and right subtree each must also be a binary search tree..

6. 2. 8. 1. 4. 3.

DELETION FROM A BINARY SEARCH TREE.

THINKS TO KEEP IN MIND TO DELETE FROM A BINARY SEARCH TREE.

Case 1 : Delete From Leaf Node. 6. 2. 8. 0. 4. 3.

Case 2: Node Having One child. In this case just send the current’s node child to its parent’s place.

6. 2. 8. 0. 4. 3.

6. 2. 8. 0. 4. 3. Delete 3. 6. 2. 8. 0. 4.

Case 3: Node has both children. Find inorder successor of the node.Copy contents of the inorder successor to the node and delete the in order successor.note that inorder predessor can also be used..

6. 8. 9. 0. 5. 7. 6.

6. 8. 9. 0. 5. 7. 6. Delete 8. 6. 7. 9. 0. 5. 7. 6.

6. 7. 9. 0. 5. 6.

6. 8. 9. 0. 5. 7. 6. Delete 8. 6. 7. 9. 0. 5. 7. 6.

Time complexity. The worst case time complexity of the delete operation is O(h) where h is the height of the binary search tree.In worst case, we may have to travel from the deepest leaf node.The height of a skewed tree may become n and the time complexity of delete operation may became O(n).

THANKS FOR WATCHING THE VIDEO TILL NOW. If any doubt in this topic comment below.