# For those who is not so clear about inorder successors.

• Here is a good explaination I found:
http://stackoverflow.com/questions/5471731/in-order-successor-in-binary-search-tree

If you have right child, do this approach (case 1 above):

If you don't have a right child, do this approach (case 2 above):

• Python solution of iterative and recursive:

#method 1: iterative :

``````def  inorderSuccessor(self,root,p):
suc=None
while root:
#     if root.val>p.val: #if root.val=p.val we still move right, cause we need find a value greater than him.
#greater value is successor candidate:
suc=root
root=root.left
else:
root=root.right
return suc
``````

#method 2: recursive:

``````def inorderSuccessor(self,root,p):
if root == None:return None
if root.val>p.val:#means root is at right side of p, then move left:
suc=self.inorderSuccessor(root.left,p)
#suc is none means this is a dead end, and since we are moving left, so successor is the previous one, which is root.
if suc !=None:
return suc
else:
return root
else:
#means root is at right side of p, it could be the successor,if it's left value
# Or it could be far right from P, then move left:
return self.inorderSuccessor(root.right,p)``````

• I method 1, p is not used???

• http://www.geeksforgeeks.org/?p=9999