Microsoft Interview Question
Country: United States
Yes, if it is not a binary tree then better consider it as a generic graph and then to find the path of a given node from source node perform depth first or breadth first search. You can understand these concepts here
DFS
youtube.com/watch?v=gCNsAKkUHPM
BFS
youtube.com/watch?v=5pNIul92cj0
I have a very basic doubt. If we are using BFS then how will we keep track of path till the parent of the first element of the queue?wont it be easier with the help of recursion in DFS?if anyone could help..
In BFS algo we maintain parent info for every node except the root(one from which BFS call is being started). Suppose v is in adjancey of u then we maintain a parent[v] = u, sort of info. So to generate the path you can write a recursive function which uses this info and print the path.
void printPath(node v, node s){
if(v == s){
printf("%s",s);
return;
}
printPath(parent(v),s);
printf("%s",parent(v));
}
struct node
{
int data;
struct node *child;
stuct node *sibling;
};
void printLeavePaths(node *root)
{
if(root == NULL)
return;
enQueue(root);
if(root->child == NULL)
{
printQueueElemts(); // With out removing the elements from the // queue
deQueue();
if(root->sibling != NULL)
{
printLeavePaths(root->sibling);
return;
}
}
if(root->child != NULL)
{
printLeavePaths(root->child);
if (root->sibling == NULL)
{
// Delete non path elemts for the new path
deQueue();
return;
}
}
if(root->sibling != NULL)
{
// Delete recently queued elem
deQueue()
printLeavePaths(root->sibling);
}
}
DFS will be sufficient. No advantage of using BFS and maintaining queue.
Also, InOrder or PreOrder or PostOrder traversal will help to find node as it is binary tree and not a BST.
traverse the whole tree
- Anonymous July 13, 2012