If we have some Binary Search Tree and perform the operations add(x) followed by remove(x) do we necessarily return to the original tree?

Question

The value of x should be the same. Do we get the same tree back again with one add and one remove operation?

Answer 1

No, not necessarily. The set of elements does not uniquely determine the structure of the tree, and there are many ways to implement a BST, with different mechanisms for adding and removing elements. Some types of BST, such as self-balancing BSTs, can adjust themselves in ways that destroy information about their previous structures, and therefore these operations are not generally reversible.

For instance, suppose we have a self-balancing BST:

  8
 / \
3   9
 \
  4

We add 5:

    8
   / \
  4   9
 / \
3   5

and remove 5:

    8
   / \
  4   9
 /
3