Question

function TreeSuccessor(x)
    if x.right != NIL
        return TreeMinimum(x.right)  // TreeMinimum is on page 291
    y = x.p   // parent
    while y != NIL and x == y.right
        x = y
        y = y.p
    return y

Tree-Minimum(x)

1 While x.left != NIL

2     x = x.left

3 return x

Consider the following algorithm.

procedure MysteryWalk(x)
    y = TreeMinimum(x)
    while y != NIL
        print y
        y = TreeSuccessor(y)

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

Answer 1

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.