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.