COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Pre-order predecessor
|
|
|
In-order predecessor
|
|
|
in-order successor
|
|
|
Post-order successor
|
Detailed explanation-1: -In this, the node which is to be deleted is replaced with its in-order successor or predecessor recursively until the node to be deleted is replaced on the leaf of the tree. After this, replace the node with NULL and free the allocated space.
Detailed explanation-2: -Deletion of a Node with two child nodes A deleted node with two children must be replaced by a value which is one of: The largest value in the deleted node’s left subtree.
Detailed explanation-3: -The node to be deleted has two children. However, the node which is to be deleted, is replaced with its in-order successor or predecessor recursively until the node value (to be deleted) is placed on the leaf of the tree.
Detailed explanation-4: -1) Node to be deleted is the leaf: Simply remove it from the tree. 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.
Detailed explanation-5: -In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of the input node. So, it is sometimes important to find next node in sorted order.