Create binary search tree class, which supports the following operations:

1. Insert

2. Search

3.Delete

4.In-order traversal

Important

1. The implementation should be template based.

2. The pointer to parent node should also be included in each node. This means each node should

have 3 pointers: left, right and parent. The insert/search/delete should accordingly.

Insert Algorithm:

BST_INSERT(node, newNode)  Input: root node of tree, node to be inserted  Output: updated tree with newNode  Steps: 1. If node == null //base case 2. node = newNode 3. Else If newNode.key < node.key 4. node.left = BST_INSERT(node.left, newNode) 5. Else If newNode.key > node.key 6. node.right = BST_INSERT(node.right, newNode) 7. End If 8. Return node 

Deletion Algorithm:

BST_DELETE(node, int key)  Input: root node of tree, key to be deleted  Output: updated tree without node that contains key  Steps: 1. If(node!=null) 2. If key ==node.key 3. If hasLeft(node) and hasRight(node) //case 3 4. successor= INORDER_SUCCESSOR(node) 5. copy(node,successor) 6. node.right= BST_DELETE(node.right, successor.key ) 7. Else //case1, case 2, you can break it in 2 if's 8. node=getChildNode(node); 9. End If 9. Else If key < node.key 10. node.left =BST_DELETE(node.left,key) 11. Else // key > node.key 12. node.right =BST_DELETE(node.right,key) 13. End If 14. return node // updated node 15. End If 16. return node // null getChildNode(node) 1. If hasLeft(node) 2. return node.left 3. Else If hasRight(node) 4. return node.right 5. Else 6. Return NULL// leaf node case 7. End if copy(node,successor) 1. node.key=successor.key 2. Copy other data attributes if present but not child links 

Search: Algorithm

 BST_SEARCH(node, key)  Input: root node of tree, key to be searched  Output: node which contains value  Steps: Start 1. If node== null OR value==node.key //one case for both value found or not found return node 2. Else If value < node.key 3. return BST_SEARCH( node.left, key) 4. Else // key> node.key 5. return BST_SEARCH( node.right, key) End 

inorder Traversal Algorithm:

 Traverse_InOrder(Tree node) If node is not NULL Recursive_InOrder(node.left) print(node) Recursive_InOrder(node.right) End If