Print a binary tree one level at a time, from the root downwards.
What to build
A level-order traversal that uses a queue of node pointers.
Requirements
- Print the values of each level on its own line, from left to right.
- Start with the root's level.
- Do not use recursion: use a queue.
Input
The first line has n. Line i of the next n lines describes node i: its value, then the numbers of its left and right children, or -1 for no child. Node 0 is the root.
Output
One line for each level of the tree.
Constraints
1 ≤ n ≤ 100.
Example
Input:
5
1 1 2
2 3 4
3 -1 -1
4 -1 -1
5 -1 -1
Output:
1
2 3
4 5
Why it works
A queue hands nodes back in the order they were found, and a node's children are always found after every node of its own level. So the tree comes out level by level.
Examples
5 1 1 2 2 3 4 3 -1 -1 4 -1 -1 5 -1 -1
1 2 3 4 5
1 9 -1 -1
9
Hints
Hint 1
Use a queue of node pointers, and start with the root in it.
Hint 2
Take a node from the front, print it, and add its children at the rear.
Hint 3
Before starting a level, remember where the rear is: every node in front of that mark belongs to the level.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
int value;
struct tree *left, *right;
} Tree;
int main(void) {
int n;
scanf("%d", &n);
Tree *nodes[100];
for (int i = 0; i < n; i++) nodes[i] = malloc(sizeof(Tree));
for (int i = 0; i < n; i++) {
int l, r;
scanf("%d %d %d", &nodes[i]->value, &l, &r);
nodes[i]->left = l == -1 ? NULL : nodes[l];
nodes[i]->right = r == -1 ? NULL : nodes[r];
}
Tree *queue[100];
int front = 0, rear = 0;
queue[rear++] = nodes[0];
while (front < rear) {
int level_end = rear; /* everything waiting now is one level */
int first = 1;
while (front < level_end) {
Tree *t = queue[front++];
if (!first) printf(" ");
first = 0;
printf("%d", t->value);
if (t->left != NULL) queue[rear++] = t->left;
if (t->right != NULL) queue[rear++] = t->right;
}
printf("\n");
}
for (int i = 0; i < n; i++) free(nodes[i]);
return 0;
}