Find the in-order successor of a given node in a binary search tree

Question

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

• user134596: I think your code is good; it's clear, easy to follow, and appears to handle the corner cases!

Answer 1

For idiomatic Python:

• You should not put spaces between the brackets and the values in function calls.
• You should use snake_case for variables.

---

You've said you have concerns over finding the parent node that is the ancestor. Lets say we have the tree:

 A
 B
C D

Since that all left nodes are smaller than the current value in binary trees we know that \$B < A\$, \$C < B\$ and \$D < A\$. We also know that the right nodes are larger than the current node, and so \$B < D\$. And so we know \$C < B < D < A\$.

From this we can see that logically if node.parent.left == node is the same as if node.parent.value > target.

The benefit to the former is you don't have to create target.

---

Your implementation is awkward, successor should always be called duplicating the input.

successor(node, node.value)

If you don't then you'll have problems. Say \$A = 1\$, and \$\text{node} = D\$. The successor to \$D\$ is \$A\$, however successor(node, 1) will incorrectly return \$B\$.

To fix this just define target_value in successor.

def successor(node):
 if node.right:
 node = node.right
 while node.left:
 node = node.left
 else:
 target_value = node.value
 while node:
 node = node.parent
 if node.value > target_value:
 break
 return node

---

If you follow what you've seen online you can reduce the amount of lines of code:

def successor(node):
 if node.right:
 node = node.right
 while node.left:
 node = node.left
 else:
 while node != node.parent.left:
 node = node.parent
 node = node.parent
 return node

---

It should be noted that if there is no successor in the tree all implementations will raise an AttributeError.

This is rather confusing, and so you may want to change it to a different error.

def successor(node):
 try:
 if node.right:
 node = node.right
 while node.left:
 node = node.left
 else:
 while node != node.parent.left:
 node = node.parent
 node = node.parent
 return node
 except AttributeError:
 raise ValueError('No successor exists.') from None

• screeb: Thanks Peilonrayz. As for the last point, I was trying to avoid throwing an exception and intended to return None upon there being no in-order successor. I didn't notice I'd throw an AttributeError when accessing the node in if node.value > targetValue. I think this can be remedied by changing this condition to if node is None or node.value > targetValue. So, we either break if the current node is the in-order successor or we've reached the top of the tree and arrived at our parent's root. This way we either return the in-order successor or None.

Answer 2

• successor(node, targetValue) does not necessarily return the in-order successor even if called with a node in a valid search tree and that node's value: what about search trees where a value can occur more than once?
• I notice no docstrings. successor() in a binary tree (I could guess that much from left and right) might be the in-order successor, target_value could clue me in the tree is a search tree, but don't make me guess.
• I have to second Peilonrayz in rejecting the possibility to call successor() with parameters that make it return something else.

Trying to reduce the amount of lines of code while sticking to comparing values seems to use more attribute accesses:

def successor(node):
 '''Return the in-order successor of node in its search-tree.'''
 if node:
 if not node.right:
 target_value = node.value
 while node.parent and node.parent.value < target_value:
 node = node.parent
 return node.parent
 node = node.right
 while node.left:
 node = node.left
 return node