Cannot recursively delete a node from this BST?

Question

New to Python. Tried implementing a BST. It works, except for the fact that I can't seem to delete nodes from it recursively:

# in class BST
def destroy(self):
    if self.left:
        self.left.destroy()
    if self.right:
        self.right.destroy()
    self = None

# in main
root = BST(60)
root.insert(40) # inserts 40 at 60's left
root.insert(50) # inserts 50 at 40's right

print root.right # prints None because nothing's there
print root.left.right # prints 50 
root.left.destroy() # is supposed to remove 40 and 50 from the tree
print root.left.right # prints 50, even though it should be None now...

The problem must be with the destroy() method, but I can't see what the problem could be.

This code wouldn't work in any programming language I know of. You'll have to update the links of the parent (depending how you want to handle the children of a node), but setting self to none I'd a nop. — Voo, Apr 29 '14 at 07:36
Actually, I did something similar in C++ and it worked: `void destroy() {if (left != NULL) left->destroy(); if (right != NULL) right->destroy(); delete this;}` — Coffee Maker, Apr 29 '14 at 07:40
Which would just cause the parent of the node to point to a deleted node (`delete this` is legal, but almost never a good idea - also easy to introduce bugs) which will best case cause an exception when iterating later or just return garbage when iterating. — Voo, Apr 29 '14 at 07:46
possible duplicate of [Python object deleting itself](http://stackoverflow.com/questions/293431/python-object-deleting-itself) — slushy, Apr 29 '14 at 10:08

score 0 · Answer 1 · edited May 23 '17 at 12:20

In Python you don't need to explicitly manage memory; here is a link to another SO question with the same main gist. From the Python docs:

Objects are never explicitly destroyed; however, when they become unreachable they may be garbage-collected. An implementation is allowed to postpone garbage collection or omit it altogether — it is a matter of implementation quality how garbage collection is implemented, as long as no objects are collected that are still reachable.

To get your code working -- you don't need to recursively destroy. In Python can do:

# in main
print root.right # prints None because nothing's there
print root.left.right # prints 50 
root.left = None
print root.left.right # AttributeError:'NoneType' object has no attribute 'right'

Cannot recursively delete a node from this BST?

1 Answers1