Tree question

Question

In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?

• A. Inorder Successor is always a leaf node
• B. Inorder successor is always either a leaf node or a node with empty left child
• C. Inorder successor may be an ancestor of the node
• D. Inorder successor is always either a leaf node or a node with empty right child

Comments

I have confusion in A) and B) Plz explain

---

is it B?

---

Plz explain by giving suitable example.

Answer 1

      option b

Inorder successor is always either a leaf node or a node with empty left child 

Comments

thanks a lot.

---

Empty left child means i didn't get it plz explain??

---

empty left child means no left child of inorder successor

Answer 2

Answer =B.

This case of deletion will come when node will have both left and right child.

So in order successor will come from right subtree tree.

In order successor will be left most child from right subtree.

So there can be two cases:-

1. The right subtree root will have left child. In that case we get successor from leftmost child

2. The root of right subtree(of the node to be deleted) has empty left tree. In that case root of right subtree will become the successor.