Level Order Traversal

Lesson 15 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

A level-order traversal (also called breadth-first) visits the tree row by row: the root first, then both its children, then all four grandchildren, and so on, instead of diving depth-first like in-order or pre-order do.

The standard way to do this is a queue: start with the root inside it, then repeatedly remove the front node, record its value, and push its children (left before right) onto the back of the queue.

Challenge

Easy

Write a function levelOrder(tree) that returns a list of every value in the tree, level by level, left to right within each level.

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
        int result[1024];
    int resultCount = levelOrder(tree, result);
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(" ");
        printf("%d", result[i]);
    }
    printf("\n");
    return 0;
}