So, you're writing a fully threaded tree...

One idea is to write two functions. The first one is recursive and doesn't actually do the insert, it instead finds either a node with the same key, or the closest matching node that does not have two children, and it reuturns the node it found. (or null if the tree is empty)

Then your other function is responsible for calling the recursive one and then it uses the ndoe returned from that, to insert the new node both into the tree and the list simultaneously.

To do that, you:

Work out which side of the node function 1 found. Lets assume it has to go on the right. Find it's right neighbour by following that node's existing

*next* link.

Okay, now insertion into the list is easy, allocate your new item and set up its prev an next links to those two nodes, and adjust those two nodes to point to the new one.

Then since in this case it goes on the right of the node you found you can set the

*right* link of that node to point to your new node.

Your new node's left and right will be NULL of course.

Make sense?

You can work out the special case for when the root is NULL.

E.g.

Code:

4
/ \
2 6
/ \ \
1 3 7

Say you want to insert 5.

You go right of 4 because 5 is greater, then you look at 6 and see that one of its children is NULL, so you return that node. Now follow 6's prev pointer and that'll get you to node 4. Then adjust 4's next to point to 5, and adjust 6's prev to point to 5. Actually I'm sure you get the idea by now...

The sentinel is needed for when you went to insert say 0 or 8 into this data structure. You'd follow 1's prev and that has to be a real node (not just a pointer) so you can set it's next pointer. You use the same sentinel node at BOTH ends of the list.