I have an implementation of an algorithm to return the in-order successor of a given node in a binary search tree. We are allowed to assume that each node in the BST has a reference to its parent node. The in-order successor of a node is the node with the next largest key. So, if we received a node with a value of 5, and the tree contained a node with the value 6, we should return the node with the value 6.
My implementation differs slightly from most I've seen online. Most solutions, when given an input node with no right child, iterate back up the tree until the node is the left child of its parent and then returns the parent. I iterate back up the tree until the node's value is greater than our input node's value and then return that node. I think this is equivalent and results in a little more compact and easier to follow implementation. Let me know if I'm overlooking something with this implementation.
def successor( node, targetValue ):
if node.right:
node = node.right
while node.left:
node = node.left
else:
while node:
node = node.parent
if node.value > targetValue:
break
return node