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

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

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