edited by
14,323 views
4 votes
4 votes

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?

  1. Inorder Successor is always a leaf node
  2. Inorder successor is always either a leaf node or a node with empty left child
  3. Inorder successor may be an ancestor of the node
  4. Inorder successor is always either a leaf node or a node with empty right child
edited by

2 Answers

5 votes
5 votes

      option b

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

2 votes
2 votes
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.

Related questions

1 votes
1 votes
1 answer
1
casberg asked Nov 23, 2021
497 views
What is the smallest and largest number of entries for 2_3 BTree (B2_3 Tree) of height 8 (i.e 8 levels) ? 255 & 6560127 & 21866561 & 255255 & 2186
1 votes
1 votes
1 answer
2
kd..... asked Apr 13, 2019
755 views
here what to do first as FIZZA and IMRAN both are unbalanced than either to do RR rotation from FIZZA-IMRAN-NAVEEN or RL rotation from IMRAN-NAVEEN-LOVELY
0 votes
0 votes
2 answers
3
sripo asked Dec 25, 2018
4,677 views
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?Does it vary for binary tree?What do you mean by internal nodes? Non roo...