Consider the following sequence of numbers: [ 20, 25, 3, 4, 14, 15, 18, 12, 9, 2, 16, 19, 17 ]

• Construct Binary Search Tree (BST)                                                                      


• Perform In-order, Pre-order and Post-order traversal                                      


• Delete 15 from the above constructed BST                                                    

Solution

Construct Binary Search Tree (BST)                                                             

Perform In-order, Pre-order and Post-order traversal                                 

In-order:

2, 3, 4, 9, 12, 14, 15, 16, 17, 18, 19, 20, 25

Pre-order:

20, 3, 2, 4, 14, 12, 9, 15, 18, 16, 17, 19, 25

Post-order:

2, 9, 12, 17, 16, 19, 18, 15, 14, 4, 3, 25, 20

Delete 15 from the above constructed BST                                                    

As 15 has only one sub-tree, that is right sub-tree, so we will apply 2^nd case of deletion.