Find the in-order successor of a given node in a binary search tree
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