Interview Question
Country: United States
Yes this is correct, though why anyone would ask you to this in a tree that is not a binary tree, I cant understand, but the essentials of a bfs search should work on a B Tree too
I am not getting the usage of stack. Why do you need the stack to track the signal element. When do you push or pop from the stack.
You need the signal element to mark the end of that particular level... I am using queues and not stack... stack will print DFS order... and here we would like BFS order right (level order) so...
So like in the given tree:
global variable (static int level = 0;)
print ("level %d: ", level)
initially Q is empty;
push root (1) to the Q;
push the signal element (say NULL) into Q;
so Q contains | (NULL) | 1 |
now (while !Q.empty())
{
elem = dequeue (Q);
if (elem == NULL)
{
level ++;
print ("\nlevel %d: ", level);
}
else
{
print ("%d ", elem);
push (children of elem into Q); /* I am assuming that since a given node can have multiple children, the child nodes are maintained as an array within the node; so traverse the array and push to the Q */
}
}
and you will get the level order printing as desired.
Does this kinda make sense?
We can do this with just two variables to keep track of the number of nodes in the given level and the next level.
As an example:
void PrintLevelOrder(Node* root)
{
if (root == null)
return;
int nodesAtCurrentLevel = 1;
int nodesAtNextLevel = 0;
Queue<Node*> items = new Queue<Node*>();
items.Enqueue(root);
while (!items.IsEmpty)
{
Node* current = items.Dequeue();
printf("Level %d : %d", nodesAtCurrentLevel, current->data);
nodesAtCurrentLevel--;
if (current->Child != null)
{
foreach (Node* child in current->Child)
{
items.Enqueue(child);
nodesAtNextLevel++;
}
}
if (nodesAtCurrentLevel == 0)
{
nodesAtCurrentLevel = nodesAtNextLevel;
nodesAtNextLevel = 0;
}
}
}
private static void PrintInOrder(Node root)
{
List<Node> currentLevel = new List<Node>();
currentLevel.Add(root);
printLevel(currentLevel);
}
private static void printLevel(List<Node> currentLevel)
{
if (currentLevel.Count == 0) return;
List<Node> nextLevel = new List<Node>();
for (int i = 0; i < currentLevel.Count; i++)
{
Console.Write(currentLevel[i].Value + " ");
nextLevel.AddRange(currentLevel[i].Children);
}
Console.WriteLine();
printLevel(nextLevel);
}
use BFS.. push the given root to a queue... following the root, push a "signal" element (such as NULL or -1 or so) to the stack... keep a global static levelCounter...
- JustCoding September 27, 2012start dequeuing the queue until it becomes empty... push the children of the dequeued element into the queue... whenever you encounter the "signal" element, increment levelCounter...
print when you deem fit...