Find the in-order successor of a given node in a binary search tree 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 &gt; targetValue:
                break

    return node
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 &lt; A\$, \$C &lt; B\$ and \$D &lt; A\$. We also know that the right nodes are larger than the current node, and so \$B &lt; D\$. And so we know \$C &lt; B &lt; D &lt; A\$.

From this we can see that logically if node.parent.left == node is the same as if node.parent.value &gt; 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 &gt; 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