Page 246 - DCAP407_DATA_STRUCTURE

Unit 13: Binary Search Trees

Figure 13.4 shows binary tree before insertion.

Figure 13.4: Binary Tree Before Insertion

Figure 13.5 shows binary tree after insertion.

Figure 13.5: Binary Tree After Insertion

13.1.3 Deleting in Binary Search Trees

If the node to be deleted has no children, we can just delete it. If the node to be deleted has one child,
then the node is deleted and the child is connected directly to the parent node.
There are mainly three cases possible for deletion of any node from a binary search tree. They are:
1. Deletion of the leaf node

2. Deletion of a node that has one child
3. Deletion of a node that has two children
We can delete an existing element from a binary search tree using the following pseudocode:
Pseudocode for Deleting a Value from a Binary Search Tree
//Purpose: Delete data object X from the Tree
//Inputs: Data object X (to be deleted), binary-search-tree node
//Effect: Do nothing if tree does not contain X;

// else, update binary search tree by deleting the node containing data object X

LOVELY PROFESSIONAL UNIVERSITY 239