Cfrtjryk

class BSTNode:

"""

Represents nodes in a binary search tree.

"""

def __init__(self, key, value=None):

    self.key = key

    self.value = value

    self.left = None

    self.right = None



def height(self):

    """Return the height of this node."""

    left_height = 1 + self.left.height() if self.left else 0

    right_height = 1 + self.right.height() if self.right else 0

    return max(left_height, right_height)



def __repr__(self):

    return "<BSTNode: key={!r}, value={!r}, id={}>".format(self.key, self.value, id(self))







class BSTException(Exception):

pass





class BST:

"""

Simple recursive binary search tree implementation.

"""

def __init__(self, NodeClass=BSTNode):

    self.BSTNode = NodeClass

    self.root = None

    self.nodes = 0

    # Updated after each call to insert

    self.newest_node = None



def find(self, find_key):

    """Return node with key find_key if it exists. If not, return None. """

    return self._findhelp(self.root, find_key)



def insert(self, new_key, value=None):

    """Insert a new node with key new_key into this BST,

    increase node count by one and return the inserted node."""

    if self.find(new_key) is not None:

        raise KeyError("This BST already contains key {0!r}".format(new_key))

    self.root = self._inserthelp(self.root, new_key, value)

    self.nodes += 1

    return self.newest_node



def height(self):

    """Return the height of this tree."""

    return self.root.height() if self.root else -1



def __iter__(self):

    """Return an iterator of the keys of this tree in sorted order."""

    for node in self._visit_inorder(self.root):

        yield node.key



def __len__(self):

    return self.nodes







def remove(self, key):

    temp=self.find(key)

    if temp != None:

        self.root = self.removehelp(self.root, key)

        self.nodes-=1

    return temp





def removehelp(self, node, key):

    if node==None:

        return None

    if node.key > key:

        node.left=self.removehelp(node.left, key)

    elif node.key < key:

        node.right=self.removehelp(node.right, key)

    else:

        if node.left==None:

            return node.right

        elif node.right == None:

            return node.left

        else:

            temp=BSTNode(self.findmax(node.left).key)

            node.key=temp.key

            node.left=self.removemax(node.left)

    return node





def removemax(self,node):

    if node.right==None:

        return node.left

    node.right=self.removemax(node.right)

    return node





def findmax(self, node):

    if node.right==None:

        return node

    return self.findmax(node.right) 





def _findhelp(self, node, find_key):

    if node == None or find_key==node.key:

        return node

    elif node.key > find_key:

        return self._findhelp(node.left, find_key)

    else:

        return self._findhelp(node.right, find_key)





def _inserthelp(self, node, new_key, value):

    if node is None:

        self.newest_node = self.BSTNode(new_key, value)

        return self.newest_node

    if node.key >= new_key:

        node.left=self._inserthelp(node.left, new_key, value)

    else:

        node.right=self._inserthelp(node.right, new_key, value)

    return node

I would need help in implementing remove method and its helper methods removehelp, removemax and findmax in BST class.

The remove method accepts as a parameter one integer, which is the key of the node to be removed. If a node with the given parameter key exists, the node is removed from the tree, the node counter is decremented and the node is returned. Else, nothing happens and None is returned

This should be basic stuff, but for some reason I don't get it right. Any assistance is greatly appreciated!