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