binary tree -print the elements according to the level

This question was asked to me in an interview:

binary tree -print the elements according to the level

lets say we have above binary tree,how can i produce an output like below

2 7 5 2 6 9 5 11 4

i answered like may be we can have a level count variable and print all the elements sequentially by checking the level count variable of each node. probably i was wrong.

can anybody give anyidea as to how we can achieve that?

--------------Solutions-------------

You need to do a breadth first traversal of the tree. Here it is described as follows:

Breadth-first traversal: Depth-first is not the only way to go through the elements of a 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
/ \
f k <-- level 1
/ \ \
a h z <-- level 2
\
d <-- level 3

people like to number things starting with 0.)

So, if we want to visit the elements level-by-level (and left-to-right, as usual), we would 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 level-by-level traversal is called a breadth-first traversal because we explore the breadth, i.e., full width of the tree at a given level, before going deeper.

The traversal in your question is called a level-order traversal and this is how it's done (very simple/clean code snippet I found).

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

enqueue F
dequeue F
enqueue B G
dequeue B
enqueue A D
dequeue G
enqueue I
dequeue A
dequeue D
enqueue C E
dequeue I
enqueue H
dequeue C
dequeue E
dequeue H

For this tree (straight from Wikipedia):
binary tree -print the elements according to the level

The term for that is level-order traversal. Wikipedia describes an algorithm for that using 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)

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);
}

Iterative deepening would also work and saves memory use, but at the expense of computing time.

If we are able to fetch the next element at same level, we are done. As per our prior knowledge, we can access these element using breadth first traversal.

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

Algorithm: 1. Put root in queue.
2. Put NULL in queue.
3. While Queue is not empty
4. x = fetch first element from queue
5. If x is not NULL
6. x->rpeer <= top element of queue.
7. put left and right child of x in queue
8. else
9. if queue is not empty
10. put NULL in queue
11. end if
12. end while
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;
}

I would use a collection, e.g. std::list, to store all elements of the currently printed level:

  1. Collect pointers to all nodes in the current level in the container
  2. Print the nodes listed in the container
  3. Make a new container, add the subnodes of all nodes in the container
  4. Overwrite the old container with the new container
  5. repeat until container is empty

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 - traverse the tree in the regular pre-order dragging a level counter along, maintaining a vector of linked-lists of pointers to nodes per level, e.g.

levels[level].push_back(&node);

and in the end print the list of each level.

Category:c# Time:2011-04-14 Views:0

Related post

  • Keeping a binary tree balanced when elements are insert in order 2011-10-30

    I was wondering if there is a suitable algorithm for maintaining the balance of a binary tree, when it is known that elements are always inserted in order. One option for this would be to use the standard method of creating a balanced tree from a sor

  • In a binary tree, print all nodes which are at a distance K from a given node 2014-02-26

    Given the root and a node in a binary tree along with an integer K. Write a method to print all the nodes which are K distance apart from the given node. This question was asked in an interview. Solution is direct if the given node is root node but h

  • Heap binary tree print method 2010-11-04

    In my assignment I know I am required to use my heap remove function which returns the variable to be printed. But the requirement in teh assignment is quite vague and I was curious if someone could give me a better explanation. I am quite confused a

  • Binary tree, print out which level I am on 2011-06-26

    I want to print out into my sorted tree on which level this number was and that must be a recursion function. Here is my code: void printout(KNOTEN *start) { if(start == NULL) return; printout(start->left); printf("%d\n",start->number); printou

  • How to find the lowest common ancestor of two nodes in any binary tree? 2009-09-27

    The Binary Tree here is may not necessarily be a Binary Search Tree. The structure could be taken as - struct node { int data; struct node *left; struct node *right; }; The maximum solution I could work out with a friend was something of this sort -

  • Finding the common ancestor in a binary tree 2011-05-30

    This question was asked to me in an interview: I have a binary tree and I have to find the common ancestor (parent) given two random nodes of that tree. I am also given a pointer to the root node. My answer is: Traverse the tree separately for both t

  • What are the applications of binary trees? 2010-01-25

    I am wondering what the particular applications of binary trees are. Could you give some real examples? --------------Solutions------------- Even though the bounty is gone, since the accepted answer gives the extremely-false impression that binary-tr

  • Implement an immutable deque as a balanced binary tree? 2010-07-17

    I've been thinking for a while about how to go about implementing a deque (that is, a double-ended queue) as an immutable data structure. There seem to be different ways of doing this. AFAIK, immutable data structures are generally hierarchical, so t

  • Difference between binary tree and binary search tree 2011-06-17

    Can anyone please explain the difference between binary tree and binary search tree with an example? --------------Solutions------------- Binary tree: Tree where each node has up to two leaves 1 / \ 2 3 Binary search tree: Used for searching. A binar

  • Level order insertion into a binary tree? 2011-07-02

    Suppose we are given a level order traversal output. How to construct a binary tree from that populated with the data at correct positions? Please note that I'm not trying to sketch the tree from the given traversal output, but read off the traversal

  • How can one add a specific part of a binary tree but keep the tree intact (Java)? 2011-07-09

    I am trying to write a code that searches a binary tree for an element and then adds starting at that element. So far I can find the correct position and add to that position, but I lose the rest of the binary tree. public void add(String addroot, St

  • Is this a Complete Binary Tree? 2011-06-28

    If this is a Complete Binary Tree, why the following is not? --------------Solutions------------- See Wikipedia: Types of binary trees A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambig

  • Algorithm question: print all the elements on a single given level of a binary tree 2010-01-23

    I am required to print out(visit) the nodes on a single level of a binary tree. I don't see how this can be done but then again I not very skilled with algorithms in general. I know that in Breadth-First traversal you use a queue and that you start b

  • How would you print out the data in a binary tree, level by level, starting at the top? 2009-07-09

    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)

  • Printing BFS (Binary Tree) in Level Order with _specific formatting_ 2009-12-12

    To begin with, this question is not a dup of this one, but builds on it. Taking the tree in that question as an example, 1 / \ 2 3 / / \ 4 5 6 How would you modify your program to print it so, 1 2 3 4 5 6 rather than the general 1 2 3 4 5 6 I'm basic

  • Java Binary Tree. Printing InOrder traversal 2010-04-24

    I am having some problems printing an inOrder traversal of my binary tree. Even after inserting many items into the tree it's only printing 3 items. public class BinaryTree { private TreeNode root; private int size; public BinaryTree(){ this.size = 0

  • How can I print a binary tree level by level 2011-03-26

    How would you print out the data in a binary tree, level by level, starting at the top, with python? I'm very new with this and I don't have any idea how to start. Any help would be greatly appreciated. from collections import deque class EmptyTree(o

  • Binary Search Tree Printing 2011-11-19

    I am working on a Binary Tree program for school and I have everything working perfectly. All I am working on now is the proper output. My teacher wants the output to be all the numbers in sorted order with commas after them. My code that I have sort

  • Printing a binary tree hierarchy using a Depth-first iterative deepening method or Breadth-First 2012-02-28

    I'm not a programmer, but I'm currently experimenting with binary trees in Python, and I'm wanting to create a good method for printing out the binary tree, level by level; currently I have implemented a breadth-first method, printing each level star

Copyright (C) pcaskme.com, All Rights Reserved.

processed in 1.141 (s). 13 q(s)