Find parent in Binary Search Tree?

Question

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 1

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

• Lozansky: That's a really neat solution! I didn't think of initializing a parent to None like that, this should help me out greatly.
• Ami Tavory: @Lozansky HTH. LMK if there's a typo or something with the code, as I just wrote it straight into the answer.