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'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

Answer 2

Here is another BST with Python, using a sorting key

LEFT = 0 RIGHT = 1 VALUE = 2 SORT_KEY = -1

class BinarySearchTree(object):

def __init__(self, sort_key=None):
    self._root = []  
    self._sort_key = sort_key
    self._len = 0  

def insert(self, val): if self._sort_key is None: sort_key = val // if no sort key, sort key is value else: sort_key = self._sort_key(val)

node = self._root
while node:
    if sort_key < node[_SORT_KEY]:
        node = node[LEFT]
    else:
        node = node[RIGHT]

if sort_key is val:
    node[:] = [[], [], val]
else:
    node[:] = [[], [], val, sort_key]
self._len += 1

def minimum(self):
    return self._extreme_node(LEFT)[VALUE]

def maximum(self):
    return self._extreme_node(RIGHT)[VALUE]

def find(self, sort_key):
    return self._find(sort_key)[VALUE]

def _extreme_node(self, side):
    if not self._root:
        raise IndexError('Empty')
    node = self._root
    while node[side]:
        node = node[side]
    return node

def _find(self, sort_key):
    node = self._root
    while node:
        node_key = node[SORT_KEY]
        if sort_key < node_key:
            node = node[LEFT]
        elif sort_key > node_key:
            node = node[RIGHT]
        else:
            return node
    raise KeyError("%r not found" % sort_key)

Sort key is replaced by value if any.