Binary tree - print elements according to level

Question

This question was asked to me in an interview:

lets say that we have over the binary tree how can I create an output as shown below

2 7 5 2 6 9 5 11 4 

I answered as if we could have a level counting variable and print all the elements sequentially, checking the level count variable of each node. I was probably wrong.

Can anyone give anyidea on how we can achieve this?

Answer 1

You need to make the width of the first tree walk. It is described as follows:

First pass: first, in depth, this is not the only way to go through the elements of the tree. Another way is to go through them level by level.

For example, each element exists at a certain level (or depth) in the tree:

  tree ---- j <-- level 0 / \ fk <-- level 1 / \ \ ahz <-- level 2 \ d <-- level 3 

people like to start at 0.)

So, if we want to visit elements by level (and from left to right, as usual), we will start at level 0 with j, then go to level 1 for f and k, then go to level 2 for a, h and z and finally go to level 3 for d.

This step-by-step walk is called width walk because we examine latitude, i.e. the full width of the tree at a given level, before going deeper.

Answer 2

The workaround in your question is called level-order traversal and this is how it is done (a very simple / clean piece of code that I found).

You basically use a queue, and the order of operations will look something like this:

 enqueue F dequeue F enqueue BG dequeue B enqueue AD dequeue G enqueue I dequeue A dequeue D enqueue CE dequeue I enqueue H dequeue C dequeue E dequeue H 

For this tree (directly from Wikipedia):

Answer 3

The term for this is level traversal. Wikipedia describes an algorithm for use in a queue :

 levelorder(root) q = empty queue q.enqueue(root) while not q.empty do node := q.dequeue() visit(node) if node.left ≠ null q.enqueue(node.left) if node.right ≠ null q.enqueue(node.right) 

Answer 4

BFS :

 std::queue<Node const *> q; q.push(&root); while (!q.empty()) { Node const *n = q.front(); q.pop(); std::cout << n->data << std::endl; if (n->left) q.push(n->left); if (n->right) q.push(n->right); } 

The iterative recess will also work and save memory, but at the expense of computational time.

Answer 5

If we can get the next item at the same level, we are done. According to our previous knowledge , we can access this element using the first width traversal.

Now the only problem is how to check if we are the last element at any level. For this reason, we must add a delimiter (NULL in this case) to mark the end of the level.

Algorithm: 1. Put root in the queue.
2. Put NULL in the queue.
3. Until the queue is empty
4.x = select the first item from the queue
5. If x is not NULL 6. x-> rpeer <= the top element of the queue.
7. put the left and right child x of the queue
8. else
9. If the queue is not empty
10. put NULL in the queue
11. end, if 12. end, and 13. return

 #include <queue> void print(tree* root) { queue<tree*> que; if (!root) return; tree *tmp, *l, *r; que.push(root); que.push(NULL); while( !que.empty() ) { tmp = que.front(); que.pop(); if(tmp != NULL) { cout << tmp=>val; //print value l = tmp->left; r = tmp->right; if(l) que.push(l); if(r) que.push(r); } else { if (!que.empty()) que.push(NULL); } } return; } 

Answer 6

I would use a collection, for example. std::list to save all elements of the current print level:

• Collect pointers to all nodes of the current level in the container
• Print the nodes listed in the container
• Create a new container, add subnodes of all nodes in the container
• Overwrite old container with new container
• repeat until container is empty.

Answer 7

as an example of what you can do at an interview, if you don’t remember / don’t know the “official” algorithm, my first idea was to cross the tree in the usual pre-order by dragging the level counter along, maintaining the vector of linked lists of pointers to nodes at the level, for example

 levels[level].push_back(&node); 

and at the end print a list of each level.