CareerCup

Coding in C is required

Heap principle will work:

For example:
LL: 0->1->2->3->4->5->6->7->8->9->10->11
Tree:
0 -> [1, 2]
1 -> [3, 4]
2 -> [5, 6]
3 -> [7, 8]
4 -> [9, 10]
5 -> [11]
6 -> X

typedef struct object Object;

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 WHICH NEED TO BE FILLED
	Object* parent_ptr; // Initialized as NULL.
	unsigned int child_count; // Initialized as 0.
	Object** child_ptr_array; // Initialized as NULL.
};

void convert_list_to_tree_helper(Object * list_head, int skip) 
{
	int c = 0;
	Object * first = list_head;
	while((c++ != skip) && first) {
		first = first->next_ptr;
	}
	
	if(!first) return;
	
	Object * second = first->next_ptr;
	if(!second) {
		list_head->child_ptr_array = (Object **)malloc(sizeof(Object *));
		list_head->child_ptr_array[0] = first;
		first->parent_ptr = list_head;
		list_head->child_count = 1;
		return;
	}
	list_head->child_ptr_array = (Object **)malloc(sizeof(Object *) * 2);
	first->parent_ptr = list_head;
	second->parent_ptr = list_head;
	list_head->child_ptr_array[0] = first;
	list_head->child_ptr_array[1] = second;
	list_head->child_count = 2;
	
	convert_list_to_tree_helper(first, 2*skip);
	convert_list_to_tree_helper(second, 2*skip + 1);
}

Object * convert_list_to_tree(Object * list_head) 
{
	convert_list_to_tree_helper(list_head, 1);
	return list_head;
}

Hi,

This method definetly convert it into binary tree, but I think you are not taking account of information available like ID and parent_ID.

I think parent and child relation is already provided and you just need to link all these parents and child.

This could be done in these steps.

1. Take Id of object, find all node which has this ID as parent_ID
update parent_ptr of child node.
increment child count to 2.
and put these two nodes in parent child array

1.1 if parent_ptr of parent node also indicate to another parent
then increment child count of that object
and update child array
repeat step 1.1 till u find parent node which has parent_ptr as NULL.

This could be code easily with C.

This should run in O(n) time.
The code Anurag have told takes O(n2) time which is not acceptable

Also ZDmytirv code isnt apt.
The solution doesnt require you to build a binary tree..
The aim is to fill the fields in each node,,and the tree is an ordinary tree

HINT: Think in terms of hash table

Anurag,

I did not understand the 1.1 part of your logic?why is this needed?

Does child_count reflect only the number of immidiate child or number of all the child of a node?

With the help of a hash table, you can fill all the parent_ptr fields by two scans of the list. Once you filled the parent_ptr, it's trial to fill child_ptr_array and child_count.

#include<iostream>
#include<map>
using namespace std;

object *convert_list_to_tree(object *list_head)
{
map<int, object *> hashmap;
object *p,*root;
int i=0;
p=list_head;
for(;p!=NULL;p=p->next_ptr)
{
    hashmap[p->ID]=p;
}
p=list_head;
for(;p!=NULL; p=p->next_ptr)
{
    if(p->parent_ID==0)
    {
    root=p;
    }
    else
    {
    p->parent_ptr=hashmap[p->parent_ID].second;
    (hashmap[p->parent_ID].second)->child_count++;
    temp_pointer=malloc(sizeof(object *));
    temp_pointer=p;
    (hashmap[p->parent_ID].second)->(*(child_ptr_array+child_count))=temp_pointer;
    }

}

return root;
}

#include<iostream>
#include<map>
using namespace std;

object *convert_list_to_tree(object *list_head)
{
map<int, object *> hashmap;
object *p,*root;
int i=0;
p=list_head;
for(;p!=NULL;p=p->next_ptr)
{
    hashmap[p->ID]=p;
}
p=list_head;
for(;p!=NULL; p=p->next_ptr)
{
    if(p->parent_ID==0)
    {
    root=p;
    }
    else
    {
    p->parent_ptr=hashmap[p->parent_ID].second;
    (hashmap[p->parent_ID].second)->child_count++;
    temp_pointer=malloc(sizeof(object *));
    temp_pointer=p;
    (hashmap[p->parent_ID].second)->(*(child_ptr_array+child_count))=temp_pointer;
    }

}

return root;
}

#include<iostream>
#include<map>
using namespace std;

object *convert_list_to_tree(object *list_head)
{
map<int, object *> hashmap;
object *p,*root;
int i=0;
p=list_head;
for(;p!=NULL;p=p->next_ptr)
{
    hashmap[p->ID]=p;
}
p=list_head;
for(;p!=NULL; p=p->next_ptr)
{
    if(p->parent_ID==0)
    {
    root=p;
    }
    else
    {
    p->parent_ptr=hashmap[p->parent_ID].second;
    (hashmap[p->parent_ID].second)->child_count++;
    temp_pointer=malloc(sizeof(object *));
    temp_pointer=p;
    (hashmap[p->parent_ID].second)->(*(child_ptr_array+child_count))=temp_pointer;
    }

}

return root;
}

#include<iostream>
#include<map>
using namespace std;

object *convert_list_to_tree(object *list_head)
{
map<int, object *> hashmap;
object *p,*root;
int i=0;
p=list_head;
for(;p!=NULL;p=p->next_ptr)
{
    hashmap[p->ID]=p;
}
p=list_head;
for(;p!=NULL; p=p->next_ptr)
{
    if(p->parent_ID==0)
    {
    root=p;
    }
    else
    {
    p->parent_ptr=hashmap[p->parent_ID].second;
    (hashmap[p->parent_ID].second)->child_count++;
    temp_pointer=malloc(sizeof(object *));
    temp_pointer=p;
    (hashmap[p->parent_ID].second)->(*(child_ptr_array+child_count))=temp_pointer;
    }

}

return root;
}