Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
I guess this is what he exepct ?
typedef struct node
{
int data;
struct node *child[N];
struct node *next
} *ptree;
ptree TraverNtree(ptree root)
{
ptree q;
for(int i=0;i<N;i++)
{
if(root->child[i]==NULL)
{
continue;
}
else
{
if (root->next==NULL) root->next=TraverNtree(root->child[i]));
else
{
q=root->next;
root->next=TraverNtree(root->child[i]));
root->next->next=q;
}
}
}
return root;
}
void treeToDoublyList(treeNode *rootNode, treeNode *& prevNode, treeNode *& head)
{
if (!rootNode)
return;
treeToDoublyList(rootNode->pLeft, prevNode, head);
rootNode->pLeft = prevNode;
if (prevNode)
prevNode->pRight = rootNode;
else
head = rootNode;
treeNode *rNode = rootNode->pRight;
head->pLeft = rootNode;
rootNode->pRight = head;
prevNode = rootNode;
treeToDoublyList(rNode, prevNode, head);
}
treeNode* treeToDoublyList(treeNode *rootNode)
{
treeNode *prev = NULL;
treeNode *head = NULL;
treeToDoublyList(rootNode, prev, head);
return head;
}
treeToLL(Node *root)
{
if (root->prev == NULL)
{
root->prev = root->left;
root->left = NULL;
}
else
{
root->left->prev = root->prev;
root->prev = root->left;
}
if (root->next == NULL)
{
root->next = root->right;
root->right = NULL;
}
else
{
root->right->next = root->next;
root->next = root->right;
}
treeToLL(root->prev);
treeToLL(root->next);
}
- Anonymous October 26, 2011