In: Computer Science
Part E (3 marks): What is the shape of a BST that is O(n) to delete the root? Draw an example with at least 8 nodes.
For Deleting Root node we have 3 cases
1)Node to be deleted has only right child: Copy the right child to the node and delete the child.
2)Node to be deleted has only left child: Copy the left child to the node and delete the child.
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Inorder predecessor can also use.
For getting O(n) time we need take 3 rd case.
In this example iam explaining Inorder succesor removal which is taking O(n) time.
If you are considering Inorder predecessor just make left child of root have more chldren in the right.
Another way is consider both inorder successor and inorder predecessor and take the best one, but there also we need to traverse entire tree.Time Complexity is always depend on how you are coding.
Here in this image iam using inorder succesor. If you want inorder predecessor and both please leave a comment below.