TreeMinimumx 1 While xleft NIL 2 x xleft 3 return x Consid

Tree-Minimum(x)

1 While x.left != NIL

2     x = x.left

3 return x

Consider the following algorithm.

Determine what this algorithm does, and compute its running time, giving a justification for your answer.

Solution

procedure MysteryWalk(x) y = TreeMinimum(x) while y != NIL print y y = TreeSuccessor(y) This procedure print all the nodes in Sorted Manner. We can say it does an Inorder Traversal of Binary Search tree Lets see How ? 1. Finds the left most child which is the minimum number. 2. Starts printing the sucessors, which means to find the next element largest than it 3. So in Binary search tree if we do in this manner which means we will get the sorted order and Results in Inorder traversal of tree. Time Complexity procedure MysteryWalk(x) y = TreeMinimum(x) ======> O(N) time, If the tree is ledt skewed we travel all the nodes so Its O(N) while y != NIL ====>We will print all the nodes that means we will traverse all at once , so while loop will run N time print y y = TreeSuccessor(y)====> Sucessor depends on height of tree , So O(h) So The Overall Time compkexity is , O(N) + O(Nh) => O(Nh) For left skewed tree if Height is N , then O(N2) Thanks , let me know if there is any concern.