However, adding predecessor and succcessor links can be difficult, if you don't think about it the "right" way. There are several reasons for having predecessor/successor links.
The main reason for adding these links is to allow you to iterate through a binary search tree efficiently. Without such links, it's fairly challenging to iterate through a BST. Even using inorder traversals (and reverse inorder), you discover that it's hard to stop, then switch directions.
The second reason is to make it harder to find code on the Internet to copy from (which you really shouldn't be doing anyway). Nearly all BST code avoids the use of predecessor/successor links, because it complicates a BST.
Finally, a BST with predecessor and successor links presents a very intriguing idea. It's the idea that a single node can appear in two different kinds of structures: in this case, a binary search tree and a doubly linked list.
On the one hand, you can think of a BST with predecessor/successor links as a BST. Just ignore the predecessor/successor links, and it's a BST.
On the other hand, you can think of it as a doubly linked list. Just ignore the left/right pointers, and it's a doubly linked list.
Have you ever seen the optical illusion that shows two faces and a vase, and it's one if you concentrate on the white part, and the other if you concentrate on the black part?
In some sense, this is what a BST with predecessor/successor links is. It's a hybrid BST and DLL. The best way to think about them is separately.
As an analogy, you are a student who may be taking 214 and 250. You have one set of grades in 214. You have another set of grades in 250. You are one person, but with two sets of grades.
Similarly, a node appears both in a BST and a DLL. Notice that these are NOT two separate structures. They are two intermingled structures.
There are several ways to do this:
Method 3 gives you the best running time. Obviously, it didn't quite come for free. You had to add the node into the tree, so that part cost you in the running time (O(n), in the worst case). But once the node has been added into the BST (using left/right pointers), it's quick to set predecessor/successor.
When you add a node to a BST, it's always added as a leaf of some parent node. This means you can conclude something very useful about the parent node: the parent of the newly added leaf node is either the predecessor or the successor of the leaf node.
Why? Let's consider one case. Suppose the node is added as the left leaf of a node. Then, by the BST property, you know that the left leaf has a value that's smaller than its parent. However, you know even more than that.
The parent node is the successor of the leaf node. By successor, I mean that if you were to print the inorder traversal, the parent would print out just after the leaf.
In fact, that's how you convince yourself that the parent is the successor. Consider the inorder traversal of a tree. Inorder traversal says to print the left subtree (recursively), then print current node, the print the right subtree (recursively).
So, what happens when the inorder traversal reaches the parent node? It prints the left subtree, which only contains the newly added leaf. Then, it prints itself. Thus, the leaf is printed just before the parent, thus the parent is the successor of the leaf.
At this point, think of the BST as a doubly linked list. If necessary, draw it as a doubly linked list and ignore left/right pointers, so you can see what's going on. Again, to reiterate the main point: a BST with predecessor/successor is basically a BST combined with a DLL (doubly linked list).
Do the following, to help you with inserting the new node
into the DLL portion of the BST.
MovieBstSortedList::Node after = parent ;
MovieBstSortedList::Node before = parent->getPred() ;
before points to the node that will be the predecessor
of the leaf node (may be NULL) and after will be the successor
of the leaf node (in this case, parent). Adjusting the predecessor/successor
pointers is just like inserting into a doubly linked list, where
locate() for the BST has given you not only the parent node which
the leaf node will be placed, but also the predecessor or the
successor. locate() gives you both, so there's no need to
traverse the BST again to find where to insert the new node.
Once you have before and after, it should be straightforward to insert the new node. Make sure you only allocate memory for the node once. That node will both be a leaf node AND a node in the DLL part of the BST.
If the newly added node is a right child, then you know the parent node is the predecessor using the same inorder traversal argument.
MovieBstSortedList::Node before = parent ;
MovieBstSortedList::Node after = parent->getSucc() ;
Again, you may have to adjust up to 4 pointers.
As a special case, you have to handle the root correctly, since it has no parent. There may be other special cases.
Be careful if you use right standard (right succcessor) or left standard (left predecessor) methods and COPY the replacement node. Copying a node may copy the incorrect left/right/pred/succ pointers. As long as you work out the steps and figure out how the pointers should be adjusted, then you should be OK.
If you didn't have predecessor/successor links, then
copying the tree would be rather straight-forward. You would
write a recursive helper function, such as:
MovieBstSortedList::Node *
MovieBstSortedList::copyRec( Node * curr ) ;
This method will copy a tree, given a pointer to some node
in a BST. It returns back the pointer to the new root
of the tree (which will be a copy of the object pointed by
curr).
To use this method, you call it on the root of the other BST, and then in the body, you call the method on the left and right subtree. This creates a copy of the left and right subtree, which you now have pointers to. Then, create a new node, set the pointers to the left and right subtree, and return the pointer to the new node.
It's basically a 6 line method.
To get the predecessor and successor to work correctly takes more work. One way is to an inorder traversal and set the links correctly as you do this. This was suggested earlier for adding a node. However, this time it makes more sense to do it, since none of the nodes have their predecessor/successors pointers set.
Another way to do it is to extend copyRec() to deal with predecessor/successors as well as left/right.
Again, recall the basic idea of using recursion:
To solve a large problem, solve smaller problems, and use the solutions to the smaller problems to solve the larger problem.
For a binary tree, the smaller problem is always the left and right subtree. Sometimes you recursively call it on the left subtree, sometimes on the right, and sometimes on both subtrees. In this case, we want to call it on both subtrees.
As in "induction", you think about your "inductive hypothesis". In this case, call it the "recursive hypothesis". What do you wish to assume?
You wish to assume that the left and right subtrees have their left and right pointers correctly set, and also their predecessors and successors correctly set (of course, they are only correctly set within the subtree itself---clearly, the node with the largest value in the copy of the left subtree has its successor as NULL. After all, we're only copying the subtree, so far).
At this point, both left and right subtrees have their nodes correctly set.
What to do next? At the "root" (it may not actually be the root, but it is the root of some subtree), we know that the successor of the largest valued node in the left subtree (if it exists) is the root, and the predecessor of the root should be the largest valued node in the left subtree.
Similarly, the successor of the "root" is the smallest value in the right subtree (if it exists) and the predecessor of the smallest value in the right subtree is the root.
However, it may be inefficient to find those two nodes again. You have to traverse left then all the way down right, or right and all the way down left to reach these nodes.
It would be nice if the recursion would do this for us. To do
this, you need to add more parameters to the recursive helper function.
We want to keep track of the smallest and largest valued node of a subtree,
and pass it up.
MovieBstSortedList::Node *
MovieBstSortedList::copyRec( Node * curr, Node * & small, Node * & large ) ;
We need to use reference pointers because the recursive calls
will modify these pointers. If you pass the pointers by value,
the recursive call will not preserve the changes to the pointers,
and so this won't do any good.
OK, so we assume that the left subtree and right subtree has been recursively copied. After calling the left subtree, we need to save small and large to temporary variables so we don't lose their values when making calls to the right subtree.
Once both subtrees are copied, we need to update the left and right pointers of the newly created node (which copies the node pointed to by curr). That's easy to do.
Then, we need to adjust the four pointers for the predecessor and successor of the copy of curr. This can now be done easily because we have access to small and large from both subtrees (we only need one of the two pointers from each subtree).
Finally, we update small and large before exiting the function (think about how this should be done).
You will need a special case if you reach an empty tree (hint: make both small and large NULL), and you will need to deal with the case when small and large are NULL.
Again, this is a more challenging way to solve the problem, but should be O(n) (the solution which traverses the tree and calls add() can be as bad as O(n2).
If this doesn't make a lot of sense, it's useful to draw a tree, and see what the recursion will do. Draw pointers and go through the exercise of tracing it.