- #1

whoareyou

- 162

- 2

So, once I get into the _delete_node operation with a node with two children, I can find the maximum value in the left subtree easily. With that idea, I came up with this:

Code:

```
else: #Last condition: two children
old = node
max_node = node._left
while (max_node._right is not None):
max_node = max_node._right
node = _BSTNode (max_node._value)
node._left = old._left
node._right = old._right
max_node = self.remove(max_node._value)
```

This can successfully delete the node at the top of the tree, but with any other node in the tree with two children, it won't work (it keeps the max_node in the original position, but replaces the deleted node correctly). Another thing is that in my profs call trace, it doesn't seem as if he is calling the remove function again to remove max_node. Any help regarding this approach would be fantastic.

Relevant Code:

Code:

```
def remove(self, key):
"""
-------------------------------------------------------
Removes a node with a value matching key from the bst.
Returns the value matched.
Use: value = bst.remove( key )
-------------------------------------------------------
Preconditions:
key - data to search for (?)
Postconditions:
returns:
value - value matching key if found,
otherwise returns None. Update structure of bst as required.
-------------------------------------------------------
"""
self._root, value = self._remove_aux(self._root, key)
return value
def _remove_aux(self, node, key):
"""
-------------------------------------------------------
Attempts to find a value matching key in a BST node. Deletes the node
if found and returns the sub-tree root.
Private recursive operation called only by remove.
Use: node, value = self._remove_aux(node, key)
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
key - data to search for (?)
Postconditions:
returns:
node - the node to search for key (_BSTNode)
value - value of node containing key if it exists, None otherwise.
-------------------------------------------------------
"""
if node is None:
# Base Case: the key is not in the tree.
value = None
elif key < node._value:
# Search the left subtree.
node._left, value = self._remove_aux(node._left, key)
elif key > node._value:
# Search the right subtree.
node._right, value = self._remove_aux(node._right, key)
else:
# Value has been found.
value = node._value
# Replace this node with another node.
node = self._delete_node(node)
self._count -= 1
if node is not None and value is not None:
# If the value was found, update the ancestor heights.
node._update_height()
return node, value
```

Code:

```
def _delete_node(self, node):
"""
-------------------------------------------------------
Removes a node from the bst.
Use: node = self._delete_node(node)
-------------------------------------------------------
Preconditions:
node - the bst node to be deleted (_BSTNode)
Postconditions:
returns:
node - the node that replaces the deleted node. This node is the node
with the maximum value in the current node's left subtree (_BSTNode)
-------------------------------------------------------
"""
# Your code here.
return node
```