Find parent in Binary Search Tree?
<p>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. </p>

<p>The idea to find a parent is like this:<br>
1)  If the value (key) does not exist, return None, None<br>
2)  If the root is equal to the value (key) then return None, root<br>
3)  Else find the value (key) and return (par, node) where par is the parent and node      </p>

<p>My function looks like this:</p>

<pre><code>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&lt;key:
            p=p.left
        elif p.item&gt;key:
            p=p.right
</code></pre>

<p>How do I handle the issue when <code>p.left</code> or <code>p.right</code> is None? </p>

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

<pre><code>if not self._exists(key):
    return None,None
</code></pre>

<p>So <code>key</code> must exist, and if it must exist, it must exist on the search path. </p>

<p>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:</p>

<pre><code>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 &lt; node.item else node, node.right
</code></pre>

python python-3.x