How to delete all nodes of a Binary Search Tree

Question

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?

Answer 1

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

Answer 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.

Answer 3

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.

Answer 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.)