Tree - for Computer Science and MCA students
Draw a Binary Search Tree for following:
27, 92, 30, 64, 94, 17, 56, 49, 76, 3, 56
Write pre-order and post-order for same.
Solution:
Similarly
| Pre-Order | 27 | 17 | 3 | 92 | 30 | 64 | 56 | 49 | 56 | 76 | 94 |
| In-Order | 3 | 17 | 27 | 30 | 49 | 56 | 56 | 64 | 76 | 92 | 94 |
| Post-Order | 3 | 17 | 56 | 49 | 56 | 76 | 64 | 30 | 94 | 92 | 27 |
Write a note on deletion of node from BST.
There can be 3 possibilities while performing delete operation in binary search tree (BST).
1. Node has no children i.e. Node to be deleted is leaf node.
2. Node to be deleted has only one child.
3. Node to be deleted has two children.
Let us take one example of BST and apply delete operation.
Case 1: Node has no children i.e. Node to be deleted is leaf node.- Let us delete the item 76. Because node 76 has no child, so we can delete it simply by providing NULL value to its parent’s right pointer. In the above tree item 64 is parent of item 76. So right pointer of node value 64 will be NULL.
Case 2: Node to be deleted has only one child.- Let us delete the item 17. It has only one node and its value is 3. The parent of item 17 is item 27. So we can delete item 17 by giving the address of item 3 to the left pointer of item 27.
Case 3: Node to be deleted has two children.- Now we want to delete item 92. Since 92 have two children. We first find out the in-order successor of item 92. In the above BST 94 is the in-order successor of 92. We will provide the left and right pointer of item 92 to the left and right pointer of item 94. After that set the right pointer of item 94 as NULL.
