Question

We are given a red-black tree T containing n keys and two keys X and Y, key X is stored in node x, wbhile key Y is stored in node y. Give an effective algorithm that determines the smallest key value stored on the path connecting x and y in T. The running time should be O(log n).

Answer 1

Solution

Algorithm
At first we have to find LCA (Least common ancestor) for x and y nodes, let's call this node L. We can find L using standard search algorithm for node. Node is least common ancestor of nodes x and y when (L->key >= X->key and L->key <= Y->key) or when (L->key <= X->key and L->key >= Y->key), finding LCA in red-black tree is similar to standard finding operation and it takes O(log N) time. After fining L we need to check smallest value on roads between L and X and on road between L and Y. Smallest key will be stored in node which will be the node before first right turn (See the Picture).

Smallest LCA(X, Y) value on the road to Y 12 First Right Turn Smallest value on 5 15 the road to X First Right 3 10 13 17 -Turn 4 7 11 14 Y 6

The LCA will be smallest value on the road from LCA to biggest from X, Y. We can find smallest value for another node with simple traversal and compare it to LCA, see the pseudo code.

Pseudo Code:

#Lets store smaller value in X
If X.key > Y.key
swap X, Y

#search for LCA
L = root
while true
#If L has LCA characteristics we stop
If L.key >= X.key && L.key <= Y.key
break
#If it bigger than X and Y we search in Left subtree
if L.key > X.key
L = L.left
#else we search in right subtree
else
L = L.right

#save LCA key as answer
ans = L.key
#while there is left turn while traversing to X
while L.key > X.key
L = L.left

#compare answer to leftmost node's key
ans = minimum(ans, L.key)

return ans

THANKS.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)