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):
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)