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:

       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
7 Years
Discussion Span
Last Post by 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.


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


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.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.