Write the TREEPREDECESSOR procedure and analyze its running

Write the TREE-PREDECESSOR procedure and analyze its running time.

Solution

TREE-MAXIMUM(X)

while right [ x ] ! = NULL

do x = right[x]

return x

TREE-MINIMUM(x)

while lef t [x ] != NULL

do x = left[x]

return x

TREE-MAXIMUM and TREE-MINIMUM take time proportional to the height of the tree O(h)

TREE-PREDECESSOR(X)

if left [ x ] ! = NULL

then return TREE-MAXIMUM( left [ x ])

y = p [ x ]

while ( y != NULL ) and ( x = left [ y ])

do x = y

y = p [ x ]

return y

Tree predecessor run in time proportional to the height of the tree.

Worst-case: Assuming that our node has no right subtree, if the tree was a binary search tree, we could find the node in O(logn) time. But worst-case, it\'s not a binary search tree; in fact, it has no structure, so every call takes O(n) time, but if we\'re consistent about how we search, the total number of steps to find the node\'s successor is at least O(n²)

Best-case: Each edge in the tree gets visited at most twice (once from parent to child and once from child to the parent)\" so the total number of nodes visited is 2n and hence O(n) worst-case bound.