Programming and DS ::- BST deletion

Question

What is the time complexity to delete the root node in right skew tree?

I knew the three cases of BST deletion:- 0 child,one child,two child.

But how can we handle this particular question

Comments

Worst case time complexity of $BST$ deletion =$O(H)$ , H=Height of tree.

Remember it is the worst case.

Take A skewed tree(left skewed /right skewed) , its height will be $n$.

Now deleting a leaf node of that tree will not take $O(H)=O(n)$, it will take $O(1)$ as it is the best case.

---

@Subhanshu.

We will find inorder successor as 2,now we will replace 1 by 2 and now we will delete the node 2 from its original position and again same process will be followed.SO i am looking into complexity of this scenerio

Because i am trying to use normal BST deletion tree deletion procedure here on the right skew tree

---

@sourav.

but to search tha leaf node(if pointer not given) you to traverse BST in O(height)= O(n), so in worst case scenario, to delete leaf node it will take O(n)

Answer 1

I think first we have to perform inorder traversal to find the successor of the node which has to be deleted then delete the​ node and put the successor as the new root so it takes O(h) where h is the height of the binary search tree

Answer 2

Complexity always will be O(1)