I have a problem that deals with reading a random access file and creating an index file, which is a file to hold the binary tree of the random access file. I have the index file created with SSN (key), relative address of the SSN in the random access file, and a left and right link. What I need to do is every time a node is inserted, compare the node with the root of the tree. If it's less than, find the first SSN record in the index file that has a left link set to a -1 (dummy) and set that link equal to the position of the node I just entered. If greater than, find the first SSN record in the index file that has a right link set to a -1 (dummy) and set that link equal to the position of the node I just entered. The links are the left and right child. The first one I find with a link of -1 is the parent of the node I just inserted. Does anyone have any ideas how to do the search? Thanks for any input.

After you check the root, you have to check the next node. If less, move left, if greater, move right. Check that node. If less... ad nauseum... until you run into your -1. That's where the new node goes.