Page 249 - DCAP407_DATA_STRUCTURE

Data Structure

The figure 13.9 represents the tree after deletion of node 15.

Figure 13.9: After Deletion

Deletion of a Node That Has Two Children

Consider figure 13.10 to understand deletion of a node that has two children. The node with the value 8
needs to be deleted and also the inorder successor of node 8 needs to be found. The inorder successor
will be copied at the location of the node. The figure 13.11 represents the tree after deletion of node
holding value 8.
Figure13.10: Before Deletion

Figure 13.11: After Deletion

Thus, 9 must be copied at the position where the value of node was 8 and the left pointer of 10 must be
set as NULL. This completes the entire deletion procedure.
Traversal of a binary search tree is the same as traversal of a binary tree which has been explained in
Unit 12.

242 LOVELY PROFESSIONAL UNIVERSITY