Lozansky Lozansky - 2 months ago 12
Python Question

Find parent in Binary Search Tree?

I wish to find the parent to a node with a certain value in a BST. My node class has attributes item (i.e the value/key), left and right.

The idea to find a parent is like this:

1) If the value (key) does not exist, return None, None

2) If the root is equal to the value (key) then return None, root

3) Else find the value (key) and return (par, node) where par is the parent and node

My function looks like this:

def findpar(self,key):
if not self._exists(key):
return None,None
elif self.root.item==key:
return None, self.root
p=self.root
found=False
while not found:
if p.left.item==key:
return p, p.left
found=True
elif p.right.item==key:
return p, p.right
found=True
elif p.item<key:
p=p.left
elif p.item>key:
p=p.right


How do I handle the issue when
p.left
or
p.right
is None?

Answer

As your code currently works, it is impossible that you're turning toward a None left or right child. This is because your code starts with

if not self._exists(key):
    return None,None

So key must exist, and if it must exist, it must exist on the search path.

It should be noted that you're effectively performing the search twice, though, which is not that efficient. Instead, you could try something like this:

def findpar(self,key):
    parent, node = None, self.root
    while True:
        if node is None:
            return (None, None)

        if node.item == key:
            return (parent, node)

        parent, node = node, node.left if key < node.item else node, node.right
Comments