Binary Search Tree in python not working

Question

class Node:
    '''represents a new node in the BST'''
    def __init__(self,key):
        self.key=key
        self.disconnect()
    def disconnect(self):
        self.left=None;
        self.right=None;
        self.parent=None;
    def __str__(self):
        return 'node with kay %s'%self.key

class BST:
    def __init__(self):
        self.root=None
    def insert(self,t):
        '''inserts a new element into the tree'''
        self.find_place(self.root,t)

    def find_place(self,node,key):
        """finds the right place of the element recursively"""
        if node is None:
            node=Node(key)
            print node
        else:
            if node.key > key:
                find_place(node.left,key)
            else:
                find_place(node.right,key)
def test():
    '''function to test if the BST is working correctly'''

i wrote the above code to implement a binary search tree but the insert method is not working as expected , it fails to add even the root element . i can't undestand the cause.

Answer 1

You have to assign the root node at some point. Also, you need to assign a new node to either node.left or node.right. You are missing this completely.

Maybe something like this:

def insert(self,t):
    '''inserts a new element into the tree'''
    if not self.root:
        self.root = Node(t)
    else:
        self.find_place(self.root,t)

def find_place(self,node,key):
    """finds the right place of the element recursively"""
    if node.key > key:   
        if not node.left:
            node.left = Node(key)
        else: 
            find_place(node.left,key)
    else:
        if not node.right:
            node.left = Node(key)
        else: 
            find_place(node.right, key)

---

In your code, you are not assigning anything. Your "algorithm" basically stops when it reaches

if node is None:
    node=Node(key)
    print node

It creates a new node, prints it and stops. No assignment. That is why self.root will always be None.

Answer 2

You're not actually adding any nodes to the tree!

Its easiest to manage the adding of the root node explicitly, as you see I did below in the insert.

A find_place function would, presumably from the name, return the parent node and also whether it's the left or right slot for the key? I've made an explicit _do_insert function below that both walks and does the insert.

From then on, you need to walk the tree, each time seeing if you recurse down a branch or whether you've reached an empty slot, where you add the new node.

It might be natural to refactor your code to put responsibility for walking the tree (and doing adds, removes and such) into the Node class.

In the code below, I ignore adding a key that is already in the tree, I just silently exit:

def insert(self,t):
    '''inserts a new element into the tree'''
    if self.root is None:
        self.root = Node(t)
    else:
        self._do_insert(self.root,t)

def _do_insert(self,parent,t):
    if t > parent.key:
        if parent.left is None:
            parent.left = Node(t)
        else:
            self._do_insert(parent.left,t)
    elif t < parent.key:
        if parent.right is None:
            parent.right = Node(t)
        else:
            self._do_insert(parent.right,t)
    else:
        # raise a KeyError or something appropriate?
        pass