Hi,

I have been give the following problem to solve:

Implement a procedure that efficiently converts a linked list into a tree.

PROBLEM BACKGROUND: Each Object in the linked list has a pointer to the next Object in the list. Each Object has an ID and knows the ID of its parent in the tree (parent_ID). IDs are unique and range from 1 to N in a list with N elements, however N is not initially known. The tree root’s parent_ID is 0, but the root’s ID is not initially known.

Objects are represented using the following structure:

typedef struct Object
    {
    // THESE FIELDS ARE ALREADY DEFINED; YOU MAY NOT MODIFY THEM
    Object* next_ptr; // Next object in list; NULL if end of list.
    unsigned int ID; // unique identifier for this object.
    unsigned int parent_ID; // 0, if object is root of tree.

    // THESE FIELDS REPRESENT THE TREE; YOU MUST FILL THEM IN
    Object* parent_ptr; // Initialized as NULL.
    unsigned int child_count; // Initialized as 0.
    Object** child_ptr_array; // Initialized as NULL.
    } Object;


YOUR TASK: Your task is to implement the following procedure:

Object* Convert_Objects_To_Tree (Object* head_object_ptr);

This procedure must:

(1) return a pointer to the root Object,
(2) fill in the parent_ptr, child_count, and child_ptr_array fields for each Object in the linked list, but
(3) not modify the next_ptr, ID, or parent_ID fields in any Object.

Can anybody help on this? The way I'm approaching this problem is to find the root node first by checking the parent ID==0 and then iterating through each Object in the linked list to find out all the children of the root node...and likewise for each node.
But I'm unable to proceed and need help on how to approach this. Thanks.