I am trying to find out inorder successor of a node in a binary search tree. I read the algorithm from "Introduction to Algorithms,Cormen" and understood it. But the problem I face is that I can't find out the parent of the node when it is needed in the algorithm. Does it require a stack? I don't want to modify my node structure which has data field, left child and right child. Waiting for some suggestions!
The algorithm is stated below:
TREE-SUCCESSOR(x)
if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do x ← y
y ← p[y]
return y