TREE INPUT : 4,1,9,3,2,5,6,8,7

please use this input

Question 1: 4 marks Build a Binary Search Tree with the given input order. You must show step by step process of inserting the inputs including both recursive calls and tree diagrams for each step. refer to the Insertitem function of Lecture 10 slides to get an idea of doing this ] N.B: Unique Input orders for each student to build the tree are given on a separate file. Write down the input order on your answer script before answering the question. You must use the assigned input order. Do not change the order. Question 2: 3 marks Write down the inorder, preorder, and post-order traversal of the tree you made in Question 1 Question 3: : 3 3 marks Delete the Left Node of level 1 from the tree you have built in Question 1. Show step-by-step procedure of deleting and draw the final status of the tree after deletion is completed Now, you have a new tree that is different from the previous tree. Delete the Right Node of level 1 from this derived tree. Show step-by-step procedure of deleting and draw the final status of the tree after deletion is completed. POINT TO BE NOTED: This assignment is prepared in such a way that every student will have different answers