Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation
computer science
Description
Answer all questions – maximum 100 marks. You must score at least 50 to pass the assignment.
1. (15 marks) Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation: preorderNext(x): return the node visited after node x in a pre-order traversal of BT. postorderNext(x): return the node visited after node x in a post-order traversal of BT. inorderNext(x): return the node visited after node x in an in-order traversal of BT.
2. (25 marks) Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.
3. (20 marks) Exercise 8.2. Illustrate what happens when the sequence 1, 5, 2, 4, 3 is added to an empty ScapegoatTree, and show where the credits described in the proof of Lemma 8.3 go, and how they are used during this sequence of additions
