This is an interview question
I think of a solution. It uses queue.
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);
Console.WriteLine(root.Value);
while (q.count > 0)
{
Node n = q.DeQueue();
if (n.left !=null)
{
Console.Writeln(n.left);
q.EnQueue(n.left);
}
if (n.right !=null)
{
Console.Writeln(n.right);
q.EnQueue(n.right);
}
}
}
Can anything think of better solution than this, which doesn't use Queue?
The topmost node of a binary tree is the root node. The level of a node is the number of edges along the unique path between it and the root node. Therefore, the root node has a level of 0. If it has children, both of them have a level of 1.
The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. A node x is there in output if x is the topmost node at its horizontal distance.
Algorithm to print nodes at given levelIf level of current node is equal to L then we will print it on screen else continue pre order traversal. If node is equal to NULL, return. If level of node is equal to L, then print node and return. Recursively traverse left and right sub trees at level L + 1.
Level by level traversal is known as Breadth-first traversal. Using a Queue is the proper way to do this. If you wanted to do a depth first traversal you would use a stack.
The way you have it is not quite standard though. Here's how it should be.
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
while (q.count > 0)
{
Node n = q.DeQueue();
Console.Writeln(n.Value); //Only write the value when you dequeue it
if (n.left !=null)
{
q.EnQueue(n.left);//enqueue the left child
}
if (n.right !=null)
{
q.EnQueue(n.right);//enque the right child
}
}
}
Edit
Here's the algorithm at work. Say you had a tree like so:
1
/ \
2 3
/ / \
4 5 6
First, the root (1) would be enqueued. The loop is then entered. first item in queue (1) is dequeued and printed. 1's children are enqueued from left to right, the queue now contains {2, 3} back to start of loop first item in queue (2) is dequeued and printed 2's children are enqueued form left to right, the queue now contains {3, 4} back to start of loop ...
The queue will contain these values over each loop
1: {1}
2: {2, 3}
3: {3, 4}
4: {4, 5, 6}
5: {5, 6}
6: {6}
7: {}//empty, loop terminates
Output:
1
2
3
4
5
6
Since the question requires printing the tree level by level, there should be a way to determine when to print the new line character on the console. Here's my code which tries to do the same by appending NewLine node to the queue,
void PrintByLevel(Node *root)
{
Queue q;
Node *newline = new Node("\n");
Node *v;
q->enque(root);
q->enque(newline);
while(!q->empty()) {
v = q->deque();
if(v == newline) {
printf("\n");
if(!q->empty())
q->enque(newline);
}
else {
printf("%s", v->val);
if(v->Left)
q-enque(v->left);
if(v->right)
q->enque(v->right);
}
}
delete newline;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With