Delete Operation in Basic Implementation of the Binary Search Tree in python
<p>I am almost done with my Binary Search Tree implementation in Python except for the Deletion operation.</p>

<p>So far, in all the use cases of the function that I have tested so far:
1. leaf nodes are deleted correctly
2. nodes with two children are deleted correctly
3. root nodes are deleted correctly</p>

<p>but I am not able to delete nodes with either the left child or the right child. my Eclipse IDE showed me that some of the statements have no effect (the statements that are underlined as yellow in the following picture), so I have tried the program in my iPython Notebook local server, but the result seems to be the same.</p>

<p>lines 43-57:
<a href="http://i.stack.imgur.com/DBgEz.png" rel="nofollow"><img src="http://i.stack.imgur.com/DBgEz.png" alt="enter image description here"></a></p>

<p>what is it that I am missing out in my python program? please help me out. Here is my code :</p>

<pre><code>prevnode = None

class Node:     
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

def insert(node,info):
    if node.data is None:
        node.data = info
    elif info &lt; node.data:
        if node.left is None:
            node.left = Node(None)
        insert(node.left,info)
    elif info &gt;= node.data:
        if node.right is None:
            node.right = Node(None)
        insert(node.right,info)

def search(node,info):
    if node is None:
        print "Node with the mentioned data is not found"
    if node.data == info:
        print "Found the node containing value held by info"
    elif info &lt; node.data and node.left is not None:
        search(node.left,info)
    elif info &gt; node.data and node.right is not None:
        search(node.right,info) 

def delete(node,info):
    global prevnode
    if info == node.data:
        print "This is the place where info is stored"
        if node.left is None and node.right is None:
            if prevnode.left is not None and prevnode.left.data == node.data:
                prevnode.left = None
                del node
            elif prevnode.right is not None and prevnode.right.data == node.data:
                prevnode.right = None
                del node 
            return                 
        elif node.left is not None and node.right is None:
            if prevnode.left is not None and prevnode.left.data == node.data:
                prevnode.left == node.left
                del node
            elif prevnode.right is not None and prevnode.right.data == node.data:
                prevnode.right == node.left
                del node
            return
        elif node.left is None and node.right is not None:
            if prevnode.left is not None and prevnode.left.data == node.data:
                prevnode.left == node.right
                del node
            elif prevnode.right is not None and prevnode.right.data == node.data:
                prevnode.right == node.right
                del node 
            return           
        elif node.left is not None and node.right is not None:
            node.data = None
            prevnode = node.right
            successor = prevnode.left
            if successor is None:
                node.data = prevnode.data
                node.right = prevnode.right
            elif successor is not None:
                while successor.left is not None:
                    prevnode = successor
                    successor = prevnode.left
                if successor.right is None:
                    node.data = successor.data
                    prevnode.left = None
                    del successor
                elif successor.right is not None:
                    prevnode.left = successor.right
                    node.data = successor.data
                    successor.right = None
                    del successor               
    elif info &lt; node.data:
        print "We will have to go to the left child of the current node"
        prevnode = node
        print "parent of the left child will be prevnode : ",prevnode.data
        delete(node.left,info)
    elif info &gt;= node.data:
        print "We will have to go to the right child of the current node"
        prevnode = node
        print "parent of the right child will be prevnode : ",prevnode.data
        delete(node.right,info)

def display(node,parent):
    if node is not None:
        print "value at this node is ",node.data
        if parent is None:
            print "it is the root node"
        else:
            print "the parent is ",parent.data
    if node.left is not None:
        display(node.left,node)
    if node.right is not None:
        display(node.right,node)
    else:
        return

BST = Node(None)
while True:
    choice = int(raw_input("Please enter your choice 1.Insert, 2.Search, 3.Delete, 4.Display, 5.Exit"))
    if choice == 1:
        num = int(raw_input("Please enter the number you wish to insert"))
        insert(BST,num)
    elif choice == 2:
        num = int(raw_input("Please enter the number you wish to find"))
        search(BST,num)
    elif choice == 3:
        num = int(raw_input("Please enter the number you wish to delete"))
        delete(BST,num)
    elif choice == 4:
        print "Displaying the Tree"
        display(BST,None)
    elif choice == 5:
        break
    else:
        print "Please enter the correct input"
</code></pre>

<p><strong>P.S: just in case there are any wrong indentations(I am pretty sure there are none though), they can be indented properly</strong></p>

<p>There is a simple typo. You're using == instead of =.</p>

<p>So instead of this:</p>

<pre><code>    elif node.left is not None and node.right is None:
        if prevnode.left is not None and prevnode.left.data == node.data:
            prevnode.left == node.left
            del node
        elif prevnode.right is not None and prevnode.right.data == node.data:
            prevnode.right == node.left
            del node
        return
    elif node.left is None and node.right is not None:
        if prevnode.left is not None and prevnode.left.data == node.data:
            prevnode.left == node.right
            del node
        elif prevnode.right is not None and prevnode.right.data == node.data:
            prevnode.right == node.right
            del node 
        return
</code></pre>

<p>You want to do this:</p>

<pre><code>    elif node.left is not None and node.right is None:
        if prevnode.left is not None and prevnode.left.data == node.data:
            prevnode.left = node.left  # Changed == to =
            del node
        elif prevnode.right is not None and prevnode.right.data == node.data:
            prevnode.right = node.left  # Changed == to =
            del node
        return
    elif node.left is None and node.right is not None:
        if prevnode.left is not None and prevnode.left.data == node.data:
            prevnode.left = node.right  # Changed == to =
            del node
        elif prevnode.right is not None and prevnode.right.data == node.data:
            prevnode.right = node.right  # Changed == to =
            del node 
        return 
</code></pre>

python