Inorder Successor

[gaurav_13191]

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

[thekashyap]

Can you post your code? If you have implemented the search using recursion you won't need to store the parent info inside each node.

[gaurav_13191]

No I have made the entire proJgram on tree operations iteratively. I just need an idea. I will code it using that.

[WaltP]

Since your nodes don't store the parent, about the only thing you can do is read all the nodes and look for your current node in the children pointers.

IMO, you need to modify your node structure to add the parent node since you are traversing up the tree.

[gaurav_13191]

Hey I found the following article on internet which provides solution to the problem:
http://stackoverflow.com/questions/3796003/find-the-successor-in-a-bst-without-using-parent-pointer

[thekashyap]

Hey I found the following article on internet which provides solution to the problem:
http://stackoverflow.com/questions/3796003/find-the-successor-in-a-bst-without-using-parent-pointer

That's what this post says !