1

I am trying to write a code to delete all nodes of a BST (each node has only three attributes, left, right and data, there are no parent pointers). The following code is what I have come up with, it deletes only the right half of the tree, keeping the left half intact. How do I modify it so that the left half is deleted as well (so that ultimately I am left with only the root node which has neither left or right subtrees)?

def delete(root):
    global last
    if root:
     delete(root.left)
     delete(root.right)
     if not (root.left or root.right):
        last = root
     elif root.left == last:
        root.left = None
     else:
        root.right = None

And secondly, can anybody suggest an iterative approach as well, using stack or other related data structure?

Improve this question

4 Answers 4

Reset to default
4

Blckknght is right about garbage collection, but in case you want to do some more complex cleanup than your example suggests or understand why your code didn't work, i'll provide an additional answer:

Your problem seems to be the elif node.left == last check.

I'm not sure what your last variable is used for or what the logic is behind it.
But the problem is that node.left is almost never equal to last (you only assign a node to the last variable if both children are already set to None, which they aren't for any of the interesting nodes (those that have children)).

If you look at your code, you'll see that in that if node.left isn't equal to last only the right child gets set to None, and thus only the right part of the subtree is deleted.

I don't know python, but this should work: 

def delete(node):
    if node:

        # recurse: visit all nodes in the two subtrees
        delete(node.left)           
        delete(node.right)

        # after both subtrees have been visited, set pointers of this node to None
        node.left = None
        node.right = None

(I took the liberty of renaming your root parameter to node, since the node given to the function doesn't have to be the root-node of the tree.)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That was neat! Thanks! Can you provide an iterative approach as well? And this process cleans up the left and right subtrees, but doesn't set the root to None. So I guess you will have to do it after the function returns.
Glad i could be of help! This was my first post on stackoverflow and it feels good answering questions :) Anyway, i actually don't know python at all, so i don't know how to do the iterative approach in python. But you're right that you can use a stack datastructure to do it iteratively. Maybe googling for "iterative tree traversal" will give some hits (the wikipedia page for example).
4

If you want to delete both subtrees, there's no need to recurse. Just set root.left and root.right to None and let the garbage collector take care of them. Indeed, rather than making a delete function in the first place, you could just set root = None and be done with it!

Edit: If you need to run cleanup code on the data values, you might want to recurse through the tree to get to all of them if the GC doesn't do enough. Tearing down the links in the tree shouldn't really be necessary, but I'll do that too for good measure:

def delete(node):
    if node:
        node.data.cleanup() # run data value cleanup code

        delete(node.left)   # recurse
        delete(node.right)

        node.data = None    # clear pointers (not really necessary)
        node.left = None
        none.right = None

You had also asked about an iterative approach to traversing the tree, which is a little more complicated. Here's a way to an traversal using a deque (as a stack) to keep track of the ancestors:

from collections import deque

def delete_iterative(node):
    stack = deque()
    last = None

    # start up by pushing nodes to the stack until reaching leftmost node
    while node:
        stack.append(node)
        node = node.left

    # the main loop
    while stack:
        node = stack.pop()

        # should we expand the right subtree?
        if node.right && node.right != last: # yes
            stack.append(node)
            node = node.right

            while node: # expand to find leftmost node in right subtree
                stack.append(node)
                node = node.left

        else: # no, we just came from there (or it doesn't exist)
            # delete node's contents
            node.data.cleanup()

            node.data = None # clear pointers (not really necessary)
            node.left = None
            node.right = None

            # let our parent know that it was us it just visited
            last = node
Improve this answer

9 Comments

Yeah, that's possible of course, but it's an interview question, where the task is to delete the nodes one by one bottom up.
The only reason I can think of for that is if the data values have some special cleanup logic that needs to be run on them. I'll update my answer to handle this, though it will end up being a lot like @Bjarke's!
@Cupidvogel, I've updated with a recursive and an iterative version. The iterative version is much more complicated, but I hope I've added enough comments to make it comprehensible. Again, if there's no special cleanup work needed on the data, simply doing root=None will be best!
Does the append method add the node to the beginning of the stack? What about the pop?
@Cupidvogel The deque class's append and pop methods both work on the end of the sequence (which I'm treating as the "top" of the stack). It also has append_left and pop_left methods for working on the start, so it's fairly arbitrary which end to use. I'm used to using append though with lists, so that's what I stuck with. You could even use a list to implement the stack, but its performance won't be as good as a deque (though it should be asymptotically the same).
|
2

An iterative post-order traversal using a stack could look like this:

def is_first_visit(cur, prev):
    return prev is None or prev.left is cur or prev.right is cur

def visit_tree(root):
    if root:
        todo = [root]
        previous = None
        while len(todo):
            node = todo[-1]
            if is_first_visit(node, previous):
                # add one of our children to the stack
                if node.left: 
                    todo.append(node.left)
                elif node.right:
                    todo.append(node.right)
                # now set previous to ourself and continue
            elif previous is node.left:
                # we've done the left subtree, do right subtree if any
                if node.right:
                    todo.append(node.right)
            else: 
                # previous is either node.right (we've visited both sub-trees)
                # or ourself (we don't have a right subtree)
                do_something(node)
                todo.pop()
            previous = node

do_something does whatever you want to call "actually deleting this node".

You can do it a bit more simply by setting an attribute on each node to say whether it has had do_something called on it yet, but obviously that doesn't work so well if your nodes have __slots__ or whatever, and you don't want to modify the node type to allow for the flag.

Improve this answer

6 Comments

That looks promising. Can you add a few more comments to your code so that I can understand it properly?
In Python, there's no free function like in C to deallocate a node. So how can do_something delete a node by itself?
@Cupidvogel: not my problem ;-) The task you've been set, "delete all nodes of a BST" is kind of nonsensical in Python, because in Python you can't explicitly delete an object. def do_something(node): node.right = node.left = None might be what you want.
Exactly. That's what I was trying to do in my code, by setting a flag to the last visited node. Then coming to the parent node, checking whether the last visited node is the current node's left or right subtree, and deleting that part accordingly. In the bottom-up approach, the deletion will start from bottom, so we will never have to delete a subtree with more than one element.
Come to think of it, if you just want to set the left and right nodes to None you could not bother with do_something at all. Instead, in the elif previous is node.left clause set node.left = None and in the else clause set node.right = None. That way you'd set the left-node to None before processing the right subtree, which maybe is more in the spirit of what you're aiming for. Makes no practical difference other than affecting the order in which the Python runtime can reclaim the nodes (assuming there are no references to them from outside the tree).
|
0

I'm not sure what you're doing with those conditions after the recursive calls, but I think this should be enough:

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root = None

As pointed out in comments, Python does not pass parameters by reference. In that case you can make this work in Python like this:

def delete(root):
  if root:
    delete(root.left)
    delete(root.right)

    root.left = None
    root.right = None

Usage:
delete(root)
root = None

As for an iterative approach, you can try this. It's pseudocode, I don't know python. Basically we do a BF search.

delete(root):
  make an empty queue Q
  Q.push(root)
  while not Q.empty:
    c = Q.popFront()
    Q.push(c.left, c.right)
    c = None

Again, this won't modify the root by default if you use it as a function, but it will delete all other nodes. You could just set the root to None after the function call, or remove the parameter and work on a global root variable.

Improve this answer

8 Comments

Setting root, which is an argument to the function (and so a local variable) to None will do nothing useful.
@Blckknght - I don't know how python arguments work, but the logic is correct. You recursively delete the subtrees and then the root. If it's not passed by reference you can just set the children to None and the root separately outside the main function, or just pass root by reference.
@Cupidvogel - probably because of what Blckknght said. You need to either pass root by reference or replace root = None with root.left = root.right = None and after the initial function call set root = None.
@Cupidvogel - I posted an iterative approach.
Well, it does the trick, but not bottom-up, rather top-down. The moment you delete the root, you don't need to delete the left or right subtrees, since they won't be accessible anyway. What I want is to delete the leaves first, then their parents, blah blah blah, until only the root is left.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.