# Deleting Nodes w/ 2 Children from a BST

• whoareyou
In summary, the conversation discusses a problem with understanding recursion and implementing the _delete_node operation in a Binary Search Tree by replacing a deleted node with the maximum value in its left subtree. The individual has attempted to write the code for this operation, but it only works for the top node and not for any other node with two children. They are seeking help to understand why their approach is not working and if there is a better way to preserve the BST structure while deleting nodes. Relevant code for the remove and _remove_aux functions is also provided.
whoareyou
I guess the problem is mostly due to the fact that I still don't understand recursion very well. What my prof is trying to do is to teach it to us by directly applying it to data structures that may use them, such as the Binary Search Tree. I've already been able to delete a node with no children and one children but a node with 2 children is very confusing. I am supposed to write the _delete_node operation. The idea is to replace the deleted node with the node containing the maximum value in its left subtree. By the way, all changes are performed on the nodes, rather than on the values in the nodes. An alternate approach would be to move values between nodes in order to preserve the BST structure (which I think would be easier).

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

It looks generally like the right approach, but I think the problem is that you don't update node's parent to point to the maximum node you find. You reassign node (at least, that's what I think
Code:
node = _BSTNode (max_node._value)
means -- unfamiliar with this language, is it Python?), but this doesn't fully remove node from the tree. Try instead starting by telling node's parent to point to the maximum node, and then modifying this new node's children.

Yes it's Python! I tried drawing out on paper what the procedure was and I came up with some new code which seems to work. I found two different cases regarding the parent node of the maximum node. Does this look correct?

Code:
        else: #Last condition: two children

parent = node
max_node = node._left

while (max_node._right is not None):
parent = max_node
max_node = max_node._right

if (parent is node):
max_node._left = None
else:
parent._right = max_node._left
max_node._left = parent

parent._update_height()
max_node._right = node._right
node = max_node

Yes, it looks better now. I'm having a bit of trouble with this line though:
Code:
max_node._left = parent
I get the line before, but not really this one -- could you briefly explain what it'll do?

I think there might even be a simpler way though. Is it possible to get access to the parent of the node you want to delete? Here would be my process:

1. Identify max_node
2. Set max_node's parent's right child to be max_node's left child
3. Set max_node's left and right children to node's left and right children
4. Tell node's parent to point to max_node

That should avoid the conditional you have in the middle and make it simpler overall -- maybe try making code for these steps and see if it works the same as your code.

I tried that, but it goes into infinite recursion:

Code:
            parent = node
max_node = node._left

while (max_node._right is not None):
parent = max_node
max_node = max_node._right

parent._right = max_node._left

max_node._left = node._left
max_node._right = node._right

node = max_node

return node

Testing with values = [36, 50, 84, 6, 65, 17, 85, 49, 42, 4, 12], if I remove 36 it works fine, however, if I remove 84, then it keeps printing 65 after it prints the BST.

Hmm. I guess what I mean is can you do something like
Code:
node.parent
to get a node's parent? Or is that covered when you assign nodes to other nodes?

No, the _BSTNode doesn't have that property.

## 1. How do you delete a node with two children from a binary search tree?

To delete a node with two children from a binary search tree, you first need to find the node that you want to delete. Then, you need to find the smallest value in the right subtree of the node (or the largest value in the left subtree) and replace the value of the node you want to delete with this value. Finally, you can delete the duplicate node in the subtree.

## 2. What is the time complexity for deleting a node with two children from a binary search tree?

The time complexity for deleting a node with two children from a binary search tree is O(h), where h is the height of the tree. This is because in the worst case scenario, you may have to traverse the entire height of the tree to find the smallest or largest value in the subtree.

## 3. Can a node with two children be deleted in constant time from a binary search tree?

No, a node with two children cannot be deleted in constant time from a binary search tree. This is because the steps involved in deleting a node with two children require traversing the tree, which takes O(h) time.

## 4. What happens to the children of a deleted node in a binary search tree?

When a node with two children is deleted from a binary search tree, the children of this node become the children of the smallest value in the right subtree (or the largest value in the left subtree) that was used to replace the deleted node.

## 5. Is it possible to delete a node with two children from a binary search tree without affecting the structure of the tree?

No, it is not possible to delete a node with two children from a binary search tree without affecting the structure of the tree. This is because deleting a node with two children requires rearranging the nodes in the tree to maintain the binary search tree property.

### Similar threads

• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Programming and Computer Science
Replies
13
Views
4K
• Engineering and Comp Sci Homework Help
Replies
11
Views
11K
• Engineering and Comp Sci Homework Help
Replies
2
Views
5K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Programming and Computer Science
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
9K
• Programming and Computer Science
Replies
7
Views
75K