Now a simpler one:
For ex. if tree is
.............|1|..............
............./..\..............
.........|2|.... |3|..........
....... / \...... / \..........
.... |4|..|5| ..|6|...|7|....
Make a list like 1-->2-->3-->4-->5-->6-->7.
Subscribe to:
Post Comments (Atom)
5 comments:
Good blog man. You will see me here frequently now onwards.
Do you want me to post solutions here? Let me know.
Thanks yash, The intention is to help people who looking for jobs..these are rather simple problems but some how people tend to get confused under pressure. So i usually discuss interview problems that i come across through my friends/colleagues.
If you get time you can post the complete solution otherwise just a hint of the solution would be good enough OR if you have something really tricky that you think people should know, you can post it. It would be good if you can post any interesting problem that you come across and you think is worth discussing.
OK here is my attempt.
typedef struct List List;
struct List
{
tree* node;
List* next;
};
static List* MAKE_LIST_NODE(tree* node)
{
List* list = malloc(sizeof(*list));
if (!list) return list;
list->node = node;
list->next = NULL;
return list;
}
List* make_list(tree* root)
{
List* start = NULL;
List* end = NULL;
List* first = MAKE_LIST_NODE(root);
if (!first) {
return -1;
}
start = first;
end = first;
while(start) {
if (start->node->left) {
end->next = MAKE_LIST_NODE(start->node->left);
if (!end->next) {
return -1;
}
end = end->next;
}
if (start->node->right) {
end->next = MAKE_LIST_NODE(start->node->right);
if (!end->next) {
return -1;
}
end = end->next;
}
start = start->next;
}
return first;
}
Hi all,
the solution presented is an elegant one. But I have some general comments.
When posting such solutions, please also post comments in the code, so that it will be easier to understand for general public.
I have my own version of the solution.
Use 2 queues. The first queue starts at root and its children are stored in the second queue. whenever, you traverse an element in a queue, you create a node in a linked list. Once first queue ends, you start from 2nd queue . again put its children in 1st queue(which got empty). Again , for each element of 2nd queue, create a node in linked list. keep alternating in the 2 queues till both of them are empty.
Post a Comment