Interview Questions And Answers 
-
How would you print out the data in a binary tree, level by level, starting at the top?
4,782 Views |
(11 votes, avg: 3.09)
Loading ...
Answers »
Our Sponsors
Our Sponsors
How would you print out the data in a binary tree, level by level, starting at the top?
4,782 Views | (11 votes, avg: 3.09)
Loading ...
Use recursion to print in post-order for the binary tree.
My solution demands a lot of extra space, but here it goes. I’m assuming each node holds one printable character, you can abstract this algorithm to hold whatever you want.
char levels_char_buffer[MAX_LEVELS][MAX_BUFFER]; //hold the information for each level of the tree.
void print_tree_level( tree* treep, int level)
{
strcat( levels_char_buffer[ level], p->data);
print_tree_level( treep->leftp, level+1);
print_tree_level( treep->rightp, level+1);
}
void print_tree( tree* treep)
{
memset( level_char_buffer, ‘ ’, sizeof( level_char_buffer); //initialize buffer
print_tree_level( treep, 0);
//dump buffer out
for ( level = 0; level < MAX_LEVEL; level++)
{
printf( “level%d: %sn”, level, level_char_buffer[level]);
}
}
use a breadth-first search…are u guys retarded or something?
As you start from the top put each element in
a queue and also its children first left and then right.After you are done Dequeue all the elements.That’s it.
Traverse the tree in pre-order using say an NSTAK traversal method.
I think all the above answers are wrong.
If you look at the way the binary tree is
I guess!!!!
stored, its stored level by level.
So you just need to print out the characters
in a array
void level_order(node* n)
{
if (n)
{
stack<node*> s1,s2;
stack<node*> *ps1, *ps2;
int flag = true;
s1.push(n->right);
s1.push(n->left);
cout << *n << ” “;
do
{
if (flag)
{
ps1 = &s1;
ps2 = &s2;
}
else
{
ps1 = &s2;
ps2 = &s1;
}
while (!ps1->empty())
{
n = ps1->top();
ps1->pop();
if (n)
{
cout << *n << ” “;
ps2->push(n->right);
ps2->push(n->left);
}
}
flag = !flag;
}
while(!ps2->empty());
}
}
Imagine the next question would be that you’re not allowed to use external storage? So you can’t use breadth-first (which seems the most obvious solution in this case).
In that case you have to write a function to find the node next to it. Little bit less trivial if the tree is not balanced.
int Printlbyl(node *head)
{
if (head != NULL)
{
printf(head->info)
Printlbyl(head->left)
Printlbyl(head->right)
}
else
return;
}
void breadthFirstPrint(node *root)
{
Queue q = new Queue();
node *temp;
q.push(root);
while(!q.isEmpty())
{
temp = q.pop();
printf(”%d”,temp->info);
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
This follows the same principle as breadthfirst search. The right answer is to use a Queue.
The BFS solution is good, but if you’re not allowed to use external memory, then you use a normal inorder (for example) and do something like this (in pseudocode):
(global) level
void inorder(Tree b,integer _level)
if (b)
if _level=level
print b
level=level+1
inorder(b.left,_level)
inorder(b.right,level)
level=level-1
The complexity is O(h*n) where h is the height of the tree
cheers
int print_level(struct node *temp, int level) {
if (temp == NULL) {
return 0;
} if (level == 1) {
printf(”%d\t”,temp->data);
return 0;
} else {
print_level(temp->left, level-1);
print_level(temp->right, level-1);
return 0;
}
}
void print(void) {
int i = 1;
int temp = hight(root);
for(i = 1; i
Traverse the elements as you do in a BFS.
A pseudo code:
while(node->left!=NULL || node->right!-NULL)
{
push(node->left) into the Queue//print the value
push(node->right) into the queue//print the value
node=pop()
}
If the tree is extremely large, external storage is likely to be disallowed by the interviewer.
BFS (using a queue) is ruled out.
Recursive DFS (Inorder) called for level = 1 to MAX_HEIGHT works but is inefficient because its called fail (stack memory overflow).
The right solution will be to traverse only once using PreOrder DFS, keep track of tree level during recursive calls and append the visited node content into an external file named like 1.txt for level 1 and 2.txt for level 2 etc.
Finally read all the files 1.txt,…,MAX_HEIGHT.txt and print contents.
File IO might be slightly slower but Async IO takes away some pain. And makes it faster than multiple traversal for each level.
Typo in 1st Paragraph:
Recursive DFS (Inorder) called for level = 1 to MAX_HEIGHT works but is inefficient because its called MAX_HEIGHT times.
int MAX_HEIGHT = GetTreeHeight(Node* Tree);
for (int height = 1 to MAX_HEIGHT)
{
VisitNodesAtHeight(height)
}
Leave an Answer/Comment