Deleting all nodes in a binary tree using O(1) auxiliary storage space?

Question

The standard algorithm for deleting all nodes in a binary tree uses a postorder traversal over the nodes along these lines:

if (root is not null) {
   recursively delete left subtree
   recursively delete right subtree
   delete root
}

This algorithm uses O(h) auxiliary storage space, where h is the height of the tree, because of the space required to store the stack frames during the recursive calls. However, it runs in time O(n), because every node is visited exactly once.

Is there an algorithm to delete all the nodes in a binary tree using only O(1) auxiliary storage space without sacrificing runtime?

Answer 1

It is indeed possible to delete all the nodes in a binary tree using O(n) and O(1) auxiliary storage space by using an algorithm based on tree rotations.

Given a binary tree with the following shape:

           u
          / \
         v   C
        / \
       A   B

A right rotation of this tree pulls the node v above the node u and results in the following tree:

        v
       / \
      A   u
         / \
        B   C

Note that a tree rotation can be done in O(1) time and space by simply changing the root of the tree to be v, setting u's left child to be v's former right child, then setting v's right child to be u.

Tree rotations are useful in this context because a right rotation will always decrease the height of the left subtree of the tree by one. This is useful because of a clever observation: it is extremely easy to delete the root of the tree if it has no left subchild. In particular, if the tree is shaped like this:

     v
      \
       A

Then we can delete all the nodes in the tree by deleting the node v, then deleting all the nodes in its subtree A. This leads to a very simple algorithm for deleting all the nodes in the tree:

while (root is not null) {
    if (root has a left child) {
        perform a right rotation
    } else {
        delete the root, and make the root's right child the new root.
    }
}

This algorithm clearly uses only O(1) storage space, because it needs at most a constant number of pointers to do a rotation or to change the root and the space for these pointers can be reused across all iterations of the loop.

Moreover, it can be shown that this algorithm also runs in O(n) time. Intuitively, it's possible to see this by looking at how many times a given edge can be rotated. First, notice that whenever a right rotation is performed, an edge that goes from a node to its left child is converted into a right edge that runs from the former child back to its parent. Next, notice that once we perform a rotation that moves node u to be the right child of node v, we will never touch node u again until we have deleted node v and all of v's left subtree. As a result, we can bound the number of total rotations that will ever be done by noting that every edge in the tree will be rotated with its parent at most once. Consequently, there are at most O(n) rotations done, each of which takes O(1) time, and exactly n deletions done. This means that the algorithm runs in time O(n) and uses only O(1) space.

In case it helps, I have a C++ implementation of this algorithm, along with a much more in-depth analysis of the algorithm's behavior. It also includes formal proofs of correctness for all of the steps of the algorithm.

Hope this helps!

Answer 2

Let me start with a serious joke: If you set the root of a BST to null, you effectively delete all the nodes in the tree (the garbage collector will make the space available). While the wording is Java specific, the idea holds for other programming languages. I mention this just in case you were at a job interview or taking an exam.

Otherwise, all you have to do is use a modified version of the DSW algorithm. Basically turn the tree into a backbone and then delete as you would a linked list. Space O(1) and time O(n). You should find talks of DSW in any textbook or online.

Basically DSW is used to balance a BST. But for your case, once you get the backbone, instead of balancing, you delete like you would a linked list.

Answer 3

Algorithm 1, O(n) time and O(1) space: Delete node immediately unless it has both children. Otherwise get to the leftmost node reversing 'left' links to ensure all nodes are reachable - the leftmost node becomes new root:

void delete_tree(Node *node) {
    Node *p, *left, *right;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && right) {
            Node *prev_p = nullptr;
            do {
                p->left = prev_p;
                prev_p = p;
                p = left;
            } while ((left = p->left) != nullptr);
            p->left = p->right;
            p->right = prev_p;       //need it on the right to avoid loop
        } else {
            delete p;
            p = (left) ? left : right;
        }
    }
}

Algorithm 2, O(n) time and O(1) space: Traverse nodes depth-first, replacing child links with links to parent. Each node is deleted on the way up:

void delete_tree(Node *node) {
    Node *p, *left, *right;
    Node *upper = nullptr;

    for (p = node; p; ) {
        left = p->left;
        right = p->right;
        if (left && left != upper) {
            p->left = upper;
            upper = p;
            p = left;
        } else if (right && right != upper) {
            p->right = upper;
            upper = p;
            p = right;
        } else {
            delete p;
            p = upper;
            if (p)
                upper = (p->left) ? p->left : p->right;
        }
    }
}

Answer 4

I'm surprised by all the answers above that require complicated operations.

Removing nodes from a BST with O(1) additional storage is possible by simply replacing all recursive calls with a loop that searches for the node and also keeps track the current node's parent. Using recursion is only simpler because the recursive calls automatically store all ancestors of the searched node in a stack. However, it's not necessary to store all ancestors. It's only necessary to store the searched node and its parent, so the searched node can be unlinked. Storing all ancestors is simply a waste of space.

Solution in Python 3 is below. Don't be thrown off by the seemingly recursive call to delete --- the maximum recursion depth here is 2 since the second call to delete is guaranteed to result in the delete base case (root node containing the searched value).

class Tree(object):
    def __init__(self, x):
        self.value = x
        self.left = None
        self.right = None


def remove_rightmost(parent, parent_left, child):
    while child.right is not None:
        parent = child
        parent_left = False
        child = child.right
    if parent_left:
        parent.left = child.left
    else:
        parent.right = child.left
    return child.value


def delete(t, q):
    if t is None:
        return None

    if t.value == q:
        if t.left is None:
            return t.right
        else:
            rightmost_value = remove_rightmost(t, True, t.left)
            t.value = rightmost_value
            return t

    rv = t
    while t is not None and t.value != q:
        parent = t
        if q < t.value:
            t = t.left
            parent_left = True
        else:
            t = t.right
            parent_left = False

    if t is None:
        return rv

    if parent_left:
        parent.left = delete(t, q)
    else:
        parent.right = delete(t, q)

    return rv


def deleteFromBST(t, queries):
    for q in queries:
        t = delete(t, q)
    return t