Design and Analysis of Algorithms: Homework

Please give your detailed answer, if the handwriting is clear, it is best to use computer typing.

3. (10 points) Design an algorithm, inorderNext(v), which returns the node visited after node v in an inorder traversal of binary tree T of size n. Analyze its worst-case running time. Your algorithm should avoid performing traversals of the entire tree