Binary Search Tree - parent node method incorrect output

Question

This function searches for a key in a Binary Search Tree and returns the parent of the node that equals key. But for some reason my output when I call this function remains as None. My testing looks like this:

bst =

    22
   /  \
 12    30
/  \  /  \
8  20 25  40

b = bst.parent_r(20)
print(b)




def parent_r(self, key):
        """
        ---------------------------------------------------------
        Returns the value of the parent node in a bst given a key.
        ---------------------------------------------------------
        Parameters:
            key - a key value (?)
        Returns:
            value - a copy of the value in a node that is the parent of the
            key node, None if the key is not found.
        ---------------------------------------------------------
        """
        assert self._root is not None, "Cannot locate a parent in an empty BST"

        parent = self.parent_r_aux(self._root, key)
        return parent

    def parent_r_aux(self, node, key):
        parent = None

        if node is None:
            return None

        lparent = self.parent_r_aux(node._left, key)
        if lparent is None:
            rparent = self.parent_r_aux(node._right, key)
        
        if node._left is not None or node._right is not None:
            if node._left._value == key or node._right._value == key:
                parent = node._value
return parent

From my testing I am expecting to get the node value, 12

Answer 1

You'll need to check if the values are found in the recursive calls, then return if so.

def parent_r_aux(self, node, key):
    if node is None:
        return None

    parent = self.parent_r_aux(node._left, key)
    if parent:
        return parent

    parent = self.parent_r_aux(node._right, key)
    if parent:
        return parent

    if node._left and node._left._value == key:
        return node
    if node._right and node._right._value == key:
        return node