Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How would you print out the data in a binary tree, level by level, starting at the top?

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?

like image 726
Learner Avatar asked Jul 09 '09 15:07

Learner


People also ask

How do you find the level of a binary tree?

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.

What is top view of binary tree?

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.

How do you print nodes of tree level wise?

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.


2 Answers

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

like image 83
CodeFusionMobile Avatar answered Oct 20 '22 01:10

CodeFusionMobile


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;
}
like image 38
Mru Avatar answered Oct 20 '22 00:10

Mru